Product of Array Except Self: Two-Pass Prefix/Suffix

LeetCode's Product of Array Except Self is a medium problem that trips people up for a simple reason: the constraint says you cannot use division. That rules out the obvious approach (multiply everything together, divide by each element), and what remains is a clean application of the forward-backward two-pass pattern.

Once you see the trick, the code is short. But the trick itself is worth understanding deeply because it shows up everywhere.

The problem

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

For example, given nums = [1, 2, 3, 4], the answer is [24, 12, 8, 6]:

• Index 0: 2 * 3 * 4 = 24
• Index 1: 1 * 3 * 4 = 12
• Index 2: 1 * 2 * 4 = 8
• Index 3: 1 * 2 * 3 = 6

Why division does not work here

Your first thought might be: compute the total product of all elements, then divide by each element. That gives you the right answer in O(n) time with O(1) space.

# Does NOT satisfy the constraint
def product_except_self_division(nums):
    total = 1
    for x in nums:
        total *= x
    return [total // x for x in nums]

Two problems. First, the problem explicitly forbids division. Second, this breaks when any element is zero (division by zero). Even if you handle zeros as special cases, the code gets messy and the interviewer will steer you toward the intended approach.

The key insight: prefix and suffix products

Here is the idea. For each index i, the product of everything except nums[i] is:

(product of everything to the left of i) * (product of everything to the right of i)

You can compute both of these with two passes through the array:

1. Forward pass: build a prefix product array where prefix[i] is the product of all elements before index i.
2. Backward pass: build a suffix product array where suffix[i] is the product of all elements after index i.

Then answer[i] = prefix[i] * suffix[i].

That is the entire algorithm. Two linear passes and a multiplication. No division anywhere.

Step-by-step walkthrough

Let's trace through nums = [1, 2, 3, 4] in detail.

Notice how each pass only looks at elements on one side. The forward pass never looks right. The backward pass never looks left. When you multiply the two together, you get the product of everything except the current element.

The code

Here is the two-pass solution in Python:

def product_except_self(nums):
    n = len(nums)
    answer = [1] * n

    # Forward pass: build prefix products in-place
    prefix = 1
    for i in range(n):
        answer[i] = prefix
        prefix *= nums[i]

    # Backward pass: multiply by suffix products
    suffix = 1
    for i in range(n - 1, -1, -1):
        answer[i] *= suffix
        suffix *= nums[i]

    return answer

Notice that we do not actually need separate prefix and suffix arrays. We build the prefix products directly into the answer array during the forward pass, then multiply in the suffix products during the backward pass. This brings the extra space down to O(1) (not counting the output array).

Let's break down what is happening:

1. Create answer filled with 1s.
2. Walk left to right. At each position, store the running prefix product, then multiply the running product by the current element. After this pass, answer[i] holds the product of everything to the left of i.
3. Walk right to left doing the same thing with a suffix product. Multiply each answer[i] by the running suffix, then update the suffix. After this pass, each element has been multiplied by the product of everything to its right.
4. Return answer.

Handling zeros

What happens when the array contains zeros? The algorithm handles it naturally. If nums = [0, 1, 2, 3]:

• Prefix products: [1, 0, 0, 0]
• Suffix products: [6, 6, 3, 1]
• Answer: [6, 0, 0, 0]

Only index 0 has a non-zero answer, because it is the only position where the product of all other elements does not include the zero. No special cases needed.

Complexity analysis

Time: O(n). Two passes through the array, each doing O(1) work per element. Total: O(n).

Space: O(1) extra. We use only two variables (prefix and suffix) beyond the output array. The problem statement says the output array does not count as extra space, so this is O(1).

The in-place two-pass approach is optimal. You need to look at every element at least once, so O(n) time is the floor. And you cannot do better than O(1) extra space.

Why interviewers like this problem

Product of Array Except Self is a favorite for a few reasons:

1. The no-division constraint forces creative thinking. Candidates who jump to division get redirected and need to pivot on the spot.
2. It tests the two-pass pattern. Many candidates who have seen the idea of prefix sums have never applied it to products. The transfer is not hard, but it requires recognizing the pattern.
3. The space optimization is a natural follow-up. Going from two separate arrays to the in-place version shows you can think about memory, not just correctness.
4. It has clean edge cases. Zeros, negative numbers, single-element arrays. All are handled without special logic if your solution is correct.

The building blocks

This problem is built on one fundamental brick that appears across many LeetCode problems:

Two-pass forward-backward

The core technique here is: make one pass left to right accumulating state, then another right to left accumulating state. At each position, the combination of both passes gives you the full context. This same pattern shows up in:

• Trapping Rain Water (prefix and suffix maximums determine water level at each position)
• Candy (left-to-right and right-to-left neighbor comparisons to assign minimum candies)
• Best Time to Buy and Sell Stock III (forward pass for max profit up to day i, backward pass for max profit from day i onward)

The reason this works is that some problems require information from both directions, but you can separate the two directions into independent passes. Each pass is simple on its own. The combination gives the full answer.

Once you internalize the forward-backward brick, Product of Array Except Self stops being a standalone problem. It becomes "forward-backward with multiplication." And when you see Trapping Rain Water, you think "forward-backward with maximums." Same brick, different operation.

From understanding to recall

You have read the two-pass solution and it clicks. But could you write it from scratch two weeks from now? The gap between understanding and recall is where most people fail in interviews.

Product of Array Except Self is a great example of this. The solution is about 10 lines of code. The logic is not complicated. But the specific detail of "store the running product before multiplying by the current element" is the kind of thing that slips away if you do not practice it.

The forward-backward two-pass is one of roughly 60 reusable building blocks that show up across hundreds of LeetCode problems. If you drill the brick itself (not just one problem that uses it), you build permanent recall. Then when you see a new problem that needs context from both directions, you do not start from zero. You reach for the brick.

Related posts

• Trapping Rain Water - Another problem solved with forward-backward passes, this time tracking running maximums
• Best Time to Buy and Sell Stock - Uses a single forward pass with a running minimum, a simpler cousin of the two-pass approach
• The Two Pointers Pattern - A related technique where both ends converge, often used alongside prefix/suffix thinking