Prefix / Suffix Product

Given an array nums, return an array answer where answer[i] is the product of every element in nums except nums[i]. You must solve it without using division and in $O(n)$ time. This is LeetCode 238, "Product of Array Except Self," and it is the cleanest introduction to the prefix-suffix decomposition pattern: the idea that the answer at each position can be split into an aggregate of everything to its left and an aggregate of everything to its right.

Why not just divide?

The obvious approach is: compute the total product of the entire array, then for each index i, divide the total by nums[i]. This works in $O(n)$ time and seems clean. But there are two problems.

First, zeros break it. If the array contains a zero, the total product is zero, and dividing zero by anything gives zero, but the correct answer for positions other than the zero might be nonzero. You could count zeros and handle each case (one zero, multiple zeros, no zeros), but it gets messy. Second, the problem explicitly forbids division. This is not an arbitrary constraint: it forces you to discover a technique that generalizes far beyond this single problem.

The two-pass idea

Think about what answer[i] actually represents. It is the product of all elements to the left of index i multiplied by the product of all elements to the right of index i. If we could precompute "the product of everything before i" and "the product of everything after i" for every position, we could multiply them together.

That is exactly what two passes accomplish. A left-to-right pass builds up prefix products, and a right-to-left pass builds up suffix products. Combining them gives the final answer.

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

Left pass (prefix products): We want left[i] to be the product of all elements before index i.

• left[0] = 1 (nothing to the left of index 0)
• left[1] = 1 (the only element to the left is nums[0] = 1)
• left[2] = 1 * 2 = 2 (product of nums[0] and nums[1])
• left[3] = 1 * 2 * 3 = 6 (product of nums[0], nums[1], and nums[2])

So left = [1, 1, 2, 6].

Right pass (suffix products): We want right[i] to be the product of all elements after index i.

• right[3] = 1 (nothing to the right of index 3)
• right[2] = 4 (only nums[3] is to the right)
• right[1] = 3 * 4 = 12
• right[0] = 2 * 3 * 4 = 24

So right = [24, 12, 4, 1].

Combine: answer[i] = left[i] * right[i].

• answer[0] = 1 * 24 = 24
• answer[1] = 1 * 12 = 12
• answer[2] = 2 * 4 = 8
• answer[3] = 6 * 1 = 6

Final answer: [24, 12, 8, 6]. You can verify: 234 = 24, 134 = 12, 124 = 8, 123 = 6.

Code: space-optimized version

The naive implementation uses two separate arrays for left and right products. But we can do better. We use the output array itself to store the left products during the first pass, then multiply in the right products during the second pass using a single running variable.

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

    # Left pass: answer[i] accumulates the product of nums[0..i-1]
    left_product = 1
    for i in range(n):
        answer[i] = left_product
        left_product *= nums[i]

    # Right pass: multiply in the product of nums[i+1..n-1]
    right_product = 1
    for i in range(n - 1, -1, -1):
        answer[i] *= right_product
        right_product *= nums[i]

    return answer

After the left pass, answer holds exactly the left prefix products. The right pass walks backward, maintaining a running product of everything seen so far from the right. At each position, it multiplies the existing left product by the current right product. The result is the product of everything except nums[i].

This uses $O(1)$ extra space beyond the output array, just the two scalar variables left_product and right_product.

The same skeleton: Trapping Rain Water

The prefix-suffix pattern is not limited to products. Consider LeetCode 42, Trapping Rain Water: given an elevation map as an array of non-negative integers, compute how much water it can trap after raining.

The water above bar i depends on two things: the tallest bar to its left (left_max[i]) and the tallest bar to its right (right_max[i]). The water level at position i is min(left_max[i], right_max[i]), and the actual water trapped is that level minus the bar's own height (if positive). To know left_max, you need a left-to-right pass tracking the running maximum. To know right_max, you need a right-to-left pass tracking the running maximum. Same skeleton, different operation: maximum instead of product, and min to combine instead of multiplication.

The structural similarity is exact. In Product Except Self, the left pass accumulates a product and the right pass accumulates a product, and you multiply them. In Trapping Rain Water, the left pass accumulates a max and the right pass accumulates a max, and you take the min of them (then subtract the height). The two-pass shape is identical.

The same skeleton: Candy

Another instance is LeetCode 135, Candy. Each child has a rating, and a child with a higher rating than a neighbor must receive more candies. A left-to-right pass enforces the left-neighbor constraint; a right-to-left pass enforces the right-neighbor constraint. At each position, the final candy count is the max of what the two passes require. Once again: left aggregate, right aggregate, combine.

The general principle

The prefix-suffix decomposition applies whenever the answer at position i depends on an aggregate of everything to its left AND an aggregate of everything to its right. A single pass in one direction can only capture one side. Two passes, one forward and one backward, capture both sides, and combining their results gives the complete answer.

The pattern has three moving parts:

• The aggregation operation used during each pass (product, max, min, sum, count, etc.)
• The combination operation that merges the left and right results (multiplication, min, max, addition, etc.)
• Whether you can fold the storage into the output array or need separate auxiliary arrays

For Product Except Self, the aggregation is multiplication and the combination is multiplication. For Trapping Rain Water, the aggregation is max and the combination is min. For Candy, the aggregation is a conditional increment and the combination is max. The skeleton stays the same; only the operators change.

Connection to the two-pass assignment pattern

The prefix-suffix product pattern and the two-pass assignment pattern share the same core idea. In two-pass assignment (as in the Candy problem), each pass enforces a directional constraint, and the final answer combines both. In prefix-suffix decomposition (as in Product Except Self), each pass accumulates a directional aggregate, and the final answer combines both. They are the same technique applied to different problem shapes: one to constraint satisfaction, the other to aggregate computation. If you understand one, you understand both.

Handling edge cases

A few things to watch for in prefix-suffix product problems:

• Zeros in the array: The two-pass approach handles zeros naturally without any special logic. If nums[i] = 0, the left product at positions after i becomes zero and the right product at positions before i becomes zero, which is exactly what we want.
• Single-element arrays: answer = [1] since the product of no elements is 1 (the multiplicative identity).
• Very large products: In languages without arbitrary-precision integers, intermediate products can overflow. Python handles this automatically, but in Java or C++ you may need to work modulo some prime or use long types.

Complexity analysis

Time complexity: $O(n)$. We make exactly two passes over the array, each doing constant work per element. The total number of operations is 2n.

Space complexity: $O(1)$ extra. The output array does not count as extra space (it is required by the problem). Beyond that, we use only two scalar variables. If we had used separate left and right product arrays, the space would be $O(n)$, but the optimized version avoids this.

This combination of linear time and constant extra space is hard to beat. The two-pass prefix-suffix decomposition is one of those techniques that, once internalized, makes an entire category of problems feel routine. Whenever you see a problem where each position's answer depends on context from both sides, think: left pass, right pass, combine.

Recognizing this pattern

You're probably looking at prefix-suffix decomposition when:

• The answer at each index depends on both "something about everything to my left" and "something about everything to my right."
• The forbidden operation is division (so you cannot just compute the total and back out one element).
• A single forward pass is provably insufficient: you need information from the future, not just the past.
• The aggregation is associative but its inverse is unavailable or unsafe (multiplication with zeros, max, min).
• Constraints are tight: $O(n)$ time and ideally $O(1)$ extra space beyond the output.

Common templates:

• Product except self: left-product pass into output, then right-product pass multiplying in. Example: Product of Array Except Self.
• Max-from-left, max-from-right, combine with min: water trapped at i is min(left_max, right_max) - height[i]. Example: Trapping Rain Water.
• Two-pass constraint propagation: enforce left-neighbor rule, then right-neighbor rule, take elementwise max. Example: Candy.
• Best buy/sell split: left pass tracks min price so far, right pass tracks max price after. Example: Best Time to Buy and Sell Stock III.
• Prefix-suffix counts: count predicate matches before/after each index. Example: Find the Highest Altitude (degenerate one-sided version) or Partition Array into Disjoint Intervals.