Product of Array Except Self: Prefix and Suffix Products in O(1) Extra Space

Problem Statement#

Given an integer array nums, return an array answer such that answer[i] is the product of every element of nums except nums[i]. The constraint that makes this interview-grade: solve it in O(n) time without using division, and ideally in O(1) extra space (the output array does not count toward space). Inputs can include zeros, which is precisely why the obvious "compute total product, divide by nums[i]" approach fails.

Why This Problem Matters#

Product of Array Except Self is one of the most-asked Amazon, Meta, and Apple phone-screen problems because it tests three things in 15 minutes: prefix-sum-style preprocessing intuition, awareness of the no-division constraint that shows up in robust numerical code, and the ability to write a tight two-pass linear algorithm without bugs. It also serves as an excellent stepping stone into segment tree and Fenwick tree (BIT) territory: the moment the array becomes mutable or queryable over arbitrary ranges, the static two-pass solution must be replaced by a tree-based structure.

Mastering this problem signals fluency in the prefix family. Once you see "answer at index i depends only on aggregates of the left part and the right part," you can solve trapping rain water, candy distribution, longest mountain, and a long list of array DP problems with the same template.

The Core Insight#

For each index i, the answer is (product of nums[0..i-1]) * (product of nums[i+1..n-1]). Define left[i] as the prefix product strictly to the left of i and right[i] as the suffix product strictly to the right. Then answer[i] = left[i] * right[i]. The boundaries are clean: left[0] = 1 and right[n - 1] = 1, because the product over an empty range is the multiplicative identity.

The naive implementation uses two extra arrays left and right for O(n) extra space. The space-optimised version reuses the output array as left, then sweeps a single right accumulator from the end, multiplying it into the output as it goes. That brings extra space down to O(1).

Why no division? With zeros in the array, dividing by nums[i] is undefined, and even with at most one zero you must special-case it. The two-pass prefix/suffix approach treats zeros uniformly: any prefix or suffix that crosses a zero contributes zero to the product, and the rest of the array still computes correctly.

For the mutable follow-up where nums[i] can change, replace the two static arrays with a segment tree storing the product of each segment. Point updates and range product queries are both O(log n). A Fenwick tree (BIT) can also store products if you avoid zeros (or store them out of band) and use multiplicative identity for empty cells.

Visual Dry Run#

Take nums = [2, 3, 4, 5].

First pass (left prefix products into res):
 res[0] = 1                        prefix=1, then prefix *= nums[0]=2 -> 2
 res[1] = 2                        prefix=2, then prefix *= nums[1]=3 -> 6
 res[2] = 6                        prefix=6, then prefix *= nums[2]=4 -> 24
 res[3] = 24                       prefix=24
 
After pass 1: res = [1, 2, 6, 24]
 
Second pass (suffix products multiplied into res, right to left):
 i=3: res[3] *= 1   -> 24,  suffix *= nums[3]=5 -> 5
 i=2: res[2] *= 5   -> 30,  suffix *= nums[2]=4 -> 20
 i=1: res[1] *= 20  -> 40,  suffix *= nums[1]=3 -> 60
 i=0: res[0] *= 60  -> 60
 
Final: [60, 40, 30, 24]

Notice the symmetry. The leftmost answer needs only the right side's product, the rightmost needs only the left side, and everything in between blends the two. The two-pass trick fuses the storage and the multiply in a way that keeps the working memory at exactly one scalar plus the output.

Solution (Optimal)#

from typing import List
 
class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        res = [1] * n
 
        # Pass 1: res[i] = product of nums[0..i-1]
        prefix = 1
        for i in range(n):
            res[i] = prefix
            prefix *= nums[i]
 
        # Pass 2: multiply by suffix product on the fly
        suffix = 1
        for i in range(n - 1, -1, -1):
            res[i] *= suffix
            suffix *= nums[i]
 
        return res

function productExceptSelf(nums) {
  const n = nums.length;
  const res = new Array(n).fill(1);
 
  // Pass 1: prefix products into res
  let prefix = 1;
  for (let i = 0; i < n; i++) {
    res[i] = prefix;
    prefix *= nums[i];
  }
 
  // Pass 2: suffix products folded in
  let suffix = 1;
  for (let i = n - 1; i >= 0; i--) {
    res[i] *= suffix;
    suffix *= nums[i];
  }
 
  return res;
}

Complexity. Time is O(n) for two linear passes. Auxiliary space is O(1) because the output array does not count and we maintain only two scalar accumulators. Compared to the division-based solution (which fails on zeros) and the naive O(n^2) solution, this is the textbook optimal.

If updates are required, build a segment tree where each leaf stores nums[i] and each internal node stores the product of its children. update(i, v) is O(log n) and productExcept(i) is query(0, i - 1) * query(i + 1, n - 1), also O(log n). A Fenwick tree (BIT) over multiplicative monoids handles point updates and prefix-product queries in O(log n), but you must guard against zeros explicitly because a BIT cannot easily "undo" a zero multiplication.

Common Mistakes#

• Using division. It fails when nums[i] is zero and is fragile under floating-point rounding for large products.
• Allocating separate left and right arrays without need. The space-optimised version reuses the output array.
• Sweeping the second pass left to right instead of right to left. The suffix accumulator must build from the end.
• Initialising prefix or suffix to 0 instead of 1. The empty-product identity is 1.
• Mishandling integer overflow in C++ or Java. Use 64-bit accumulators when the spec allows large products. Python handles big integers natively.
• Forgetting that res[0] and res[n - 1] need a multiplicative identity from the missing side. Using 1 as the seed for both prefix and suffix makes this automatic.

Interview Tips#

• Open by ruling out division explicitly: "I will avoid division because zeros break it and the problem also forbids it." That sentence is worth 10 percent of the credit.
• Sketch the prefix and suffix arrays first; only then collapse to the in-place two-pass version. Building intuition before micro-optimising is what senior interviewers reward.
• State the invariant after each pass: after pass 1, res[i] equals the prefix product strictly to the left; after pass 2, res[i] equals the full answer.
• Mention the segment tree and Fenwick tree (BIT) upgrade for the mutable variant. "If nums[i] can change, I would build a segment tree of products and answer each query in O(log n)." This signals interview maturity.
• Ask about overflow if the language is C++ or Java. Even simple problems hide trap doors.

Follow-up Questions#

• Mutable variant. nums[i] can be updated; report productExceptSelf for any index. Build a segment tree of products.
• Range product queries. Generalise to productInRange(l, r). Same segment tree, different query.
• Modular variant. Compute everything modulo a prime; division returns thanks to modular inverses, but only when the modulus is prime and elements are coprime.
• Handle zeros explicitly. If at least two zeros exist, the answer is all zeros. If exactly one zero exists, only that index has a non-zero answer.
• Streaming variant. Maintain prefix products with a Fenwick tree as new elements arrive; revoking elements is harder because the multiplicative monoid is not a group when zeros appear.

Key Takeaways#

• The answer at index i factorises into the prefix product to the left and the suffix product to the right; both are computable in a single pass each.
• Avoid division: it breaks on zeros and forces ugly special cases.
• Use the output array as scratch space and one scalar accumulator to hit O(1) extra space.
• Initialise both prefix and suffix to 1, the multiplicative identity, so endpoints work without conditionals.
• For the mutable follow-up, switch to a segment tree of products with O(log n) updates and queries.
• The same prefix-and-suffix decomposition pattern solves trapping rain water, candy distribution, longest mountain, and many array DP problems.