What pattern does Product of Array Except Self use?

The Pattern: Prefix Sum (Prefix and Postfix Product Arrays) The Heuristic: When a problem requires combining all elements except the current one without division, break the problem into prefix and postfix computations that can be combined to produce the final result efficiently.

Product of Array Except Self — Prefix Sum

Q: What is the time complexity of Product of Array Except Self?

O(n). The algorithm makes two linear passes over the input array: one forward pass to compute prefix products and one backward pass to compute postfix products and combine results. Each pass is O(n), resulting in overall O(n) time.

Problem

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i]. You must solve it without using division and in O(n) time.

2 ≤ nums.length ≤ 10⁵
−30 ≤ nums[i] ≤ 30
The product of any prefix or suffix of nums fits in a 32-bit integer.

Example

Input: nums = [1,2,3,4]

Output: [24,12,8,6]

A brute-force approach would multiply all elements except the current one for each index, resulting in O(n²) time. Instead, the algorithm uses prefix and postfix products to compute the result in O(n) time without division. First, it computes prefix products: for each index i, the product of all elements before i. For nums = [1,2,3,4], prefix products are [1,1,2,6]. Then, it computes postfix products in reverse: for each index i, the product of all elements after i. Multiplying prefix and postfix products for each index gives the final answer: - index 0: prefix=1, postfix=24 (2*3*4), product=24 - index 1: prefix=1, postfix=12 (3*4), product=12 - index 2: prefix=2, postfix=4 (4), product=8 - index 3: prefix=6, postfix=1, product=6 This approach avoids division and achieves linear time complexity.

Approach

Straightforward Solution

A naive approach multiplies all elements except the current one for each index, resulting in O(n²) time, which is too slow for large inputs.

Core Observation

The product of all elements except the current one can be expressed as the product of all elements before it (prefix) multiplied by the product of all elements after it (postfix). This decomposition allows computation without division.

Path to Optimal

Recognizing the problem's multiplicative structure, the key insight is to precompute prefix products in a forward pass and postfix products in a backward pass. Multiplying these two for each index yields the desired result in O(n) time without division. This approach leverages the distributive property of multiplication and avoids redundant computations.

Optimal Approach

Initialize an output array with 1s. In the first pass, fill it with prefix products: for each index, store the product of all elements before it. In the second pass (backward), maintain a running postfix product and multiply it with the prefix product stored in the output array. This yields the final product except self for each index in O(n) time and O(1) extra space (excluding output).

Time

O(n)

The algorithm makes two linear passes over the input array: one forward pass to compute prefix products and one backward pass to compute postfix products and combine results. Each pass is O(n), resulting in overall O(n) time.

Space

O(n)

The output array of size n stores the final results. The algorithm uses only a few extra variables for prefix and postfix products, so auxiliary space is O(1). The output array space is required by the problem.

Solution

Python

1class Solution:
  def productExceptSelf(self, nums: List[int]) -> List[int]:
      n = len(nums)
      res = [1] * n
5
      prefix = 1
      for i in range(n):
          res[i] = prefix
          prefix *= nums[i]
      
      postfix = 1
      for i in range(n - 1, -1, -1):
          res[i] *= postfix
          postfix *= nums[i]
      
      return res

Step-by-Step Solution

1

Compute Prefix Products and Store in Result Array

3n = len(nums)
4res = [1] * n
6prefix = 1
7for i in range(n):
8    res[i] = prefix
9    prefix *= nums[i]

Objective

To accumulate the product of all elements before each index and store it in the result array.

Key Insight

By iterating from left to right and maintaining a running product, the algorithm efficiently captures the prefix product for each position without extra space. Storing these prefix products in the result array sets the foundation for combining with postfix products later.

Interview Quick-Check

Core Logic

The prefix product at each index is the product of all elements before it, computed cumulatively in a single forward pass.

State & Boundaries

Initialize prefix as 1 before the loop to correctly handle the first element, which has no elements before it.

Common Pitfalls & Bugs

Failing to update the prefix product after assigning it to the result array leads to incorrect prefix values for subsequent indices.

2

Combine Postfix Products with Prefix Products in Reverse Pass

11postfix = 1
12for i in range(n - 1, -1, -1):
13    res[i] *= postfix
14    postfix *= nums[i]

Objective

To multiply the stored prefix products by the product of all elements after each index, computed in a backward pass.

Key Insight

Maintaining a running postfix product while iterating backward allows the algorithm to combine postfix and prefix products in-place, avoiding extra arrays. This step completes the calculation of the product of all elements except the current one for each index.

Interview Quick-Check

Core Logic

The postfix product at each index is the product of all elements after it, computed cumulatively in a single backward pass and multiplied with the prefix product stored in the result array.

State & Boundaries

Initialize postfix as 1 before the backward loop to correctly handle the last element, which has no elements after it.

Common Pitfalls & Bugs

Multiplying the postfix product before updating it with the current element ensures the current element is excluded from its own product.

3

Return the Final Result Array

16	`return res`

Objective

To output the array containing the product of all elements except self for each index.

Key Insight

After combining prefix and postfix products, the result array holds the correct values for each position. Returning it completes the solution.

Interview Quick-Check

Core Logic

Returning the result array provides the final answer as required by the problem.

Line Analysis

This solution has 1 Critical line interviewers watch for.

Line 13 Critical

res[i] *= postfix

Multiply the current result at index i by the postfix product.

This multiplication is the core step that merges prefix and postfix computations, enabling the product except self without division or extra arrays.

Line 8 Core

res[i] = prefix

Assign the current prefix product to the result at index i.

Storing the prefix product here captures the product of all elements before index i, which will later be combined with postfix products.

Line 4 Core

res = [1] * n

Initialize the result array with 1s for all positions.

Starting with 1s allows multiplication accumulation without affecting the product, serving as a neutral element for multiplication.

Line 9 Core

prefix *= nums[i]

Update the prefix product by multiplying with the current element nums[i].

This update prepares the prefix product for the next index, ensuring it accumulates all elements up to the current one.

Line 14 Core

postfix *= nums[i]

Update the postfix product by multiplying with the current element nums[i].

This update prepares the postfix product for the next index in the backward iteration, accumulating all elements after the current one.

Line 6 Standard

prefix = 1

Initialize prefix product accumulator to 1.

Prefix starts at 1 because the product of zero elements before the first index is 1, ensuring correct multiplication for the first element.

Line 11 Standard

postfix = 1

Initialize postfix product accumulator to 1.

Postfix starts at 1 because the product of zero elements after the last index is 1, ensuring correct multiplication for the last element.

Line 7 Standard

for i in range(n):

Iterate forward through the array indices.

This loop computes prefix products for each index, building the product of all elements before the current index.

Line 12 Standard

for i in range(n - 1, -1, -1):

Iterate backward through the array indices.

This loop computes postfix products for each index, building the product of all elements after the current index.

Line 16 Standard

return res

Return the result array containing the product of all elements except self.

Returning the result completes the function, providing the final answer as required by the problem.

Line 3 Basic

n = len(nums)

Cache the length of the input array nums.

Storing the length avoids repeated calls to len(nums) and clarifies the iteration bounds for subsequent loops.

Test Your Understanding

Why does multiplying prefix and postfix products for each index correctly compute the product of all elements except the current one?

Because the prefix product at index i is the product of all elements before i, and the postfix product is the product of all elements after i. Multiplying these two excludes the element at i itself, yielding the product of all other elements.

Don't just read it. Drill it.

Reconstruct Product of Array Except Self from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Start drilling Product of Array Except Self for free

1	`class Solution:`
2	`def productExceptSelf(self, nums: List[int]) -> List[int]:`
3	`n = len(nums)`
4	`res = [1] * n`
5
6	`prefix = 1`
7	`for i in range(n):`
8	`res[i] = prefix`
9	`prefix *= nums[i]`
10
11	`postfix = 1`
12	`for i in range(n - 1, -1, -1):`
13	`res[i] *= postfix`
14	`postfix *= nums[i]`
15
16	`return res`

3	`n = len(nums)`
4	`res = [1] * n`
6	`prefix = 1`
7	`for i in range(n):`
8	`res[i] = prefix`
9	`prefix *= nums[i]`

Problem

Example

Approach

Solution

Step-by-Step Solution

Compute Prefix Products and Store in Result Array

Combine Postfix Products with Prefix Products in Reverse Pass

Return the Final Result Array

Line Analysis

Test Your Understanding

Related Problems

Don't just read it. Drill it.