238. Product of Array Except Self - Detailed Explanation

Problem statement

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].
The solution must be implemented without using division and should run in O(n) time.

This question belongs to the prefix sum family. A running product from the left, then a second pass from the right, replaces a nested loop over every pair. Here the two indices run in opposite directions: one sweeps left to right building prefix products, the other sweeps right to left building suffix products. That shape recurs across array questions, which is why it sits among the recurring coding interview patterns and why this question appears on the Blind 75 list.

Example inputs and outputs

Input: nums = [1, 2, 3, 4]
Output: [24, 12, 8, 6]
Explanation: The product of all elements except nums[i] is:
- answer[0] = 2 * 3 * 4 = 24
- answer[1] = 1 * 3 * 4 = 12
- answer[2] = 1 * 2 * 4 = 8
- answer[3] = 1 * 2 * 3 = 6
Input: nums = [-1, 1, 0, -3, 3]
Output: [0, 0, 9, 0, 0]
Explanation: Zeros need care. Every index except the one holding 0 produces a product that includes that 0, so the result is 0. The index of the single 0 in the input has output 9, the product of -1 * 1 * -3 * 3. With more than one zero in the input, all outputs would be 0.
Input: nums = [4, 5, 1, 8, 2]
Output: [80, 64, 320, 40, 160]
(Each output is the product of all input numbers except the one at that position.)

Constraints

2 <= nums.length <= 10^5
-30 <= nums[i] <= 30
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

Hints for solving the problem

Can you compute the product of all elements efficiently, without a separate pass for each index? Think about reusing computations.
Instead of division, maintain a left product and a right product for each position. Prefix and suffix products like these let you compute the result in two linear passes.

Approach 1: brute force (O(n²))

The direct approach iterates over each element and computes the product of all other elements in a nested loop. It is easy to write. It is also inefficient for large inputs, because its running time is quadratic.

Code (brute force)

Brute force approach (Python)

Python3

. . . .

Brute force approach (Java)

Java

. . . .

This brute force solution computes the result correctly, but it performs O(n) work for each of the n indices, which gives O(n²) time complexity. It is too slow once n grows large, for example to 10^5.

Approach 2: optimal solution using prefix and suffix products (O(n))

The optimal solution runs in linear time by computing products in two passes, with no division.

The idea is to calculate the prefix product, the product of all elements to the left of the current index, and the suffix product, the product of all elements to the right of the current index. Multiply the two for each position to get the result for that index.

How it works: We first traverse the array from the left, accumulating a running product. For each index i, store the product of all elements before it in a result array. Then traverse from the right end. For each index, multiply the existing value, which is the left product, by the running product of all elements to the right. That yields the final product for each index, and the index never multiplies in its own value.

Code (optimal prefix and suffix)

Python implementation

Python3

. . . .

Java implementation

Java

. . . .

In this optimal approach, each element of the output combines the product of everything to the left of that index with the product of everything to the right. We use the result array itself to hold the left products in the first loop, then update it with the right products in the second loop. The approach runs in O(n) time and uses constant extra space, aside from the output array. The same two pass construction is taught step by step in the Product of Array Except Self lesson in Grokking the Coding Interview.

Complexity analysis

Brute force: Time complexity is O(n²) and space complexity is O(1), not counting the output array. That is too slow for large n.
Optimal prefix and suffix: Time complexity is O(n) and space complexity is O(1) auxiliary. We keep only a few extra variables, aside from the output array the question requires. This meets the stated requirements.

Edge cases to consider

Array containing zero: One or more zeros in the array need special attention. With exactly one zero in nums, every position except the zero's own position reports 0, because each of those products includes that zero. With two or more zeros, every output element is 0.
Negative numbers: Negative values do not threaten correctness, but the sign of each product has to come out right. An even count of negatives yields a positive product, an odd count yields a negative one. Prefix and suffix multiplication handles the signs on its own, as long as the multiplication itself is correct.
All elements are the same: For instance, nums = [3, 3, 3] should produce [9, 9, 9]. Confirm that the algorithm does not reuse data from the same index, or do anything else that breaks this symmetrical case.

Common mistakes

Using division to get the result: A naive approach computes the total product of all numbers, then divides by nums[i] for each index. It breaks when nums contains a zero, since division by zero is undefined, and the question forbids division anyway.
Incorrect initialization of the right product accumulator: Failing to reset the running product before the suffix pass produces wrong answers. Make sure right_product in Python, or rightProduct in Java, starts at 1 before the right to left traversal.
Overwriting values too early: With a single array holding results, take care not to overwrite a value you still need. Running the prefix pass first and the suffix pass second, as shown above, keeps the values you need available at each step.

Alternative variations

Allowing division: If the question allowed division, you could compute the product of all elements and return total_product / nums[i] for each index. That is O(n) time, but it breaks on zeros and the question rules it out.
Using prefix and suffix arrays explicitly: Rather than storing prefix products in the output array, you can use two separate arrays L and R of length n. Here L[i] is the product of the elements up to i, excluding i itself, and R[i] is the product of the elements from the end down to i, again excluding i. Then set answer[i] = L[i] * R[i]. This costs O(n) extra space, which some readers trade happily for the clearer shape. The approach shown above avoids separate arrays for prefix and suffix.

Prefix sum and prefix product questions: These precompute cumulative sums or products, which cuts the work for range queries and exclusion queries. Practicing them strengthens your grasp of the technique.
Two pointer questions on arrays and strings: A compact second example is Increasing Triplet Subsequence, which tracks two running values in a single pass. A string variant worth a look is Reverse Words in a String, where two indices walk toward each other.
LeetCode 53, Maximum Subarray: This question sums rather than multiplies, yet it uses the same idea of accumulating results as you move, through Kadane's algorithm. It helps you get comfortable with running computations.
LeetCode 152, Maximum Product Subarray: This one tracks running products, including negatives and zeros, and adds its own turn on the prefix and suffix idea, since you track both the maximum and the minimum product. It makes a good next step after Product of Array Except Self.