Product of Array Except Self — The Prefix × Suffix Trick That Google Loves

Problem Statement

LeetCode 238 — Product of Array Except Self

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 product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

Example 1:

Input:  nums = [1, 2, 3, 4]
Output: [24, 12, 8, 6]

Example 2:

Input:  nums = [-1, 1, 0, -3, 3]
Output: [0, 0, 9, 0, 0]

Constraints:

• 2 <= nums.length <= 10^5
• -30 <= nums[i] <= 30
• Division is explicitly forbidden

• Why This Problem Matters
• Why Division Doesn't Work
• Building The Insight
• The O(1) Space Optimization
• Visual Dry Run
• Common Mistakes
• Pattern Recognition
• Solutions
• Python — O(n) Space (Two Explicit Arrays, Clear)
• Python — O(1) Extra Space (Optimized, Interview-Ready)
• JavaScript — O(n) Space (Two Explicit Arrays, Clear)
• JavaScript — O(1) Extra Space (Optimized, Interview-Ready)
• Complexity Analysis
• O(n) Space Version
• O(1) Space Version (Optimized)
• Follow-Up Questions
• This Pattern Solves
• Key Takeaway

Why This Problem Matters

LeetCode 238 consistently shows up at Google, Meta (Facebook), Amazon, Apple, and Microsoft interviews. It is not popular by accident. Interviewers pick it because it simultaneously tests three things that separate strong candidates from average ones:

1. Decomposition thinking. The moment you read the problem, your brain wants to reach for division — "just compute the total product and divide each element out." That reflex is your enemy here. The problem is designed to block that path, which forces you to re-frame the question: can I compute what I need from a different angle entirely?

2. The prefix/suffix accumulation pattern. Once you realize that the product of everything except nums[i] is simply "everything to the left of i" multiplied by "everything to the right of i," you have discovered one of the most versatile patterns in competitive programming and interviews. This exact decomposition — left accumulation × right accumulation — appears in dozens of other problems.

3. Space optimization under pressure. After you arrive at the working O(n) space solution, a good interviewer will immediately ask: "Can you do it with O(1) extra space?" The answer requires a small but clever insight about how you can collapse the right-side pass into a single running variable. Candidates who can make this leap cleanly stand out.

This is why Google's interviewers reportedly use it as a litmus test: it is approachable enough that most candidates can find some solution, but the optimal solution reveals how fluently a candidate thinks about trade-offs.

Why Division Doesn't Work

Before getting to the right solution, it is worth understanding why the wrong solution fails, because the problem statement's "no division" constraint is not arbitrary — it is protecting you from a trap.

The naive approach is seductive:

total = product of all elements in nums
answer[i] = total / nums[i]

This is O(n) and seems correct. But it breaks catastrophically in one scenario: zeros.

• One zero in the array: total becomes 0, and 0 / nums[i] is 0 for every index. But the correct answer for the zero's own index should be the product of all other elements (which is non-zero). You'd have to special-case this entire branch.
• Two or more zeros: total is 0, every answer should be 0 — but you still cannot compute 0 / 0 for the zero elements. Division by zero is undefined.
• Languages with integer division: Even if zeros weren't a problem, integer division loses precision for negative numbers in many languages.

So the "no division" constraint is not just a trick to make the problem harder — it is pointing you toward the solution that actually works without special-casing: the prefix × suffix approach.

Building The Insight

Let's think about what answer[i] really is. Take the array [1, 2, 3, 4] and focus on index i = 2 (value 3).

The product of all elements except 3 is 1 × 2 × 4 = 8.

Now split that differently:

• Everything to the LEFT of index 2: 1 × 2 = 2
• Everything to the RIGHT of index 2: 4
• Answer: 2 × 4 = 8 ✓

This is the fundamental insight:

answer[i] = (product of all elements to the LEFT of i) × (product of all elements to the RIGHT of i)

Now the path forward is clear. You need two arrays:

• left[i] = product of nums[0] through nums[i-1]
• right[i] = product of nums[i+1] through nums[n-1]

Then answer[i] = left[i] * right[i].

Building these is straightforward with two passes:

Left pass (left to right): Start with left[0] = 1 (nothing is to the left of index 0). For each subsequent index, left[i] = left[i-1] * nums[i-1].

Right pass (right to left): Start with right[n-1] = 1 (nothing is to the right of the last index). For each preceding index, right[i] = right[i+1] * nums[i+1].

This O(n) space solution is clean and correct, and it completely sidesteps the division problem and the zero edge case.

The O(1) Space Optimization

The O(n) space solution requires two auxiliary arrays of size n. The interviewer follow-up is almost guaranteed: "Can you do it in O(1) extra space?"

The key observation is that you do not actually need to store the entire right-products array at the same time. You can fold the right pass into a running variable.

Here is the insight step by step:

Step 1: Use the output array itself to store the left products. After this pass, answer[i] holds the product of everything to the LEFT of i. This is perfectly valid — you are filling the output array you were going to return anyway.

Step 2: Now traverse right to left with a single variable right_product = 1. At each index i:

• Multiply answer[i] (the left product already stored there) by right_product (the accumulated right product so far).
• Then update right_product *= nums[i] so the next index to the left picks up this element too.

Why does this work? When you process index i in the right-to-left pass, right_product holds the product of all elements to the RIGHT of i (every element you have visited so far in this reverse pass). You multiply that into answer[i], which already holds the left product. The result is exactly left × right = answer[i].

The trick is timing: update answer[i] first, then update right_product. This way right_product always represents "everything strictly to the right of the current index," not including nums[i] itself.

No extra arrays. One output array, one integer variable. O(1) extra space.

Visual Dry Run

Let's trace through nums = [1, 2, 3, 4] step by step.

Left pass — fill answer with prefix products:

After left pass: answer = [1, 1, 2, 6]

Right pass — multiply in running right product:

We start with right_product = 1 and traverse from right to left.

Final answer: [24, 12, 8, 6] ✓

At every step, right_product contains the product of all elements that have been visited in the reverse pass — which is exactly "everything to the right of the current index."

Common Mistakes

1. Including nums[i] itself in the prefix or suffix. When building left[i], it should be the product of everything BEFORE index i, not including nums[i]. A common error is writing left[i] = left[i-1] * nums[i] instead of left[i] = left[i-1] * nums[i-1]. Always verify with index 0: left[0] must be 1 (no elements to its left), and left[1] must be just nums[0].

2. Getting the right pass update order wrong. In the O(1) solution, you must multiply answer[i] *= right_product BEFORE updating right_product *= nums[i]. Swapping this order means nums[i] gets included in its own product — exactly the error the problem is asking you to avoid.

3. Not handling zeros correctly in follow-up discussions. If an interviewer asks you to adapt the solution for zero-counting or division-based approaches, remember: one zero means all answers are 0 except at the zero's own index; two or more zeros mean all answers are 0. The prefix/suffix approach handles this automatically and correctly without any special-casing.

4. Forgetting that the output array does not count toward space complexity. A common candidate mistake is saying "this solution is O(n) space" for the optimized version. The LeetCode problem statement explicitly says the output array does not count. You use the output array as working space in the left pass — that is allowed. The only extra space is the right_product integer variable, making it genuinely O(1).

5. Attempting a brute-force O(n²) nested loop. Some candidates compute the product for each index by looping over all other elements. This is O(n²) time and will time out on large inputs. Always push toward the prefix/suffix observation when you see a "product of everything except self" style prompt.

Pattern Recognition

The core technique here is the prefix accumulation pattern, which generalizes beyond just products:

Whenever you need to compute something about "everything to the left" and "everything to the right" of each position, think prefix/suffix arrays.

You will see this exact pattern in:

• Prefix sums (range sum queries, subarray sum equals k)
• Prefix XOR (finding XOR of subarrays in O(1))
• Trapping Rain Water (LeetCode 42) — for each position, take the min of the max-height to the left and max-height to the right
• Largest Rectangle in Histogram (LeetCode 84) — left/right boundary arrays
• Product of Last K Numbers (LeetCode 1352) — prefix product array on a stream
• Maximum Width Ramp (LeetCode 962) — suffix maximum arrays

Once you recognize this pattern, the implementation becomes mechanical: one left-to-right pass, one right-to-left pass.

Solutions

Python — O(n) Space (Two Explicit Arrays, Clear)

def productExceptSelf(nums: list[int]) -> list[int]:
    n = len(nums)

    # left[i] = product of all elements to the LEFT of index i
    left = [1] * n
    for i in range(1, n):
        left[i] = left[i - 1] * nums[i - 1]

    # right[i] = product of all elements to the RIGHT of index i
    right = [1] * n
    for i in range(n - 2, -1, -1):
        right[i] = right[i + 1] * nums[i + 1]

    # answer[i] = left product * right product
    return [left[i] * right[i] for i in range(n)]

Python — O(1) Extra Space (Optimized, Interview-Ready)

def productExceptSelf(nums: list[int]) -> list[int]:
    n = len(nums)
    answer = [1] * n

    # Pass 1: fill answer[i] with the product of everything to the LEFT of i
    # answer[0] stays 1 (nothing to the left)
    for i in range(1, n):
        answer[i] = answer[i - 1] * nums[i - 1]

    # Pass 2: multiply in the product of everything to the RIGHT of i
    # right_product accumulates as we move right-to-left
    right_product = 1
    for i in range(n - 1, -1, -1):
        # answer[i] currently holds left product; multiply by right product
        answer[i] *= right_product
        # Now include nums[i] for the next index to the left
        right_product *= nums[i]

    return answer

JavaScript — O(n) Space (Two Explicit Arrays, Clear)

function productExceptSelf(nums) {
    const n = nums.length;

    // left[i] = product of all elements strictly to the LEFT of index i
    const left = new Array(n).fill(1);
    for (let i = 1; i < n; i++) {
        left[i] = left[i - 1] * nums[i - 1];
    }

    // right[i] = product of all elements strictly to the RIGHT of index i
    const right = new Array(n).fill(1);
    for (let i = n - 2; i >= 0; i--) {
        right[i] = right[i + 1] * nums[i + 1];
    }

    // Combine: answer[i] = product of left side * product of right side
    return left.map((leftProd, i) => leftProd * right[i]);
}

JavaScript — O(1) Extra Space (Optimized, Interview-Ready)

function productExceptSelf(nums) {
    const n = nums.length;
    const answer = new Array(n).fill(1);

    // Pass 1 (left to right): answer[i] = product of everything left of i
    for (let i = 1; i < n; i++) {
        answer[i] = answer[i - 1] * nums[i - 1];
    }

    // Pass 2 (right to left): multiply in the running right product
    let rightProduct = 1;
    for (let i = n - 1; i >= 0; i--) {
        // Combine stored left product with accumulated right product
        answer[i] *= rightProduct;
        // Extend the right product to include nums[i] for the next (leftward) index
        rightProduct *= nums[i];
    }

    return answer;
}

Complexity Analysis

O(n) Space Version

O(1) Space Version (Optimized)

Both versions are optimal in time. The optimized version wins on space by collapsing the suffix array into a single running variable, using the output array as the working buffer for prefix products.

Follow-Up Questions

Interviewers at top companies almost always push further after you solve the base problem. Here are the most common follow-ups and how to think about them:

1. "What if the array contains zeros?" The prefix/suffix solution handles zeros automatically and correctly — no special-casing needed. Walk through an example with one zero (e.g., [1, 0, 3, 4]) to show the interviewer you understand: left and right arrays will naturally produce a 0 in every position except the zero's own index. For the zero's index, left[i] will be the product of all elements before it, and right[i] will be the product of all elements after it — their product is the correct answer.

2. "Can you solve it if division is allowed, and does that change the approach for zeros?" The division approach requires counting zeros first (0, 1, or 2+ zeros lead to three different code paths). This is more complex and error-prone than the prefix/suffix approach, which is another reason interviewers prefer the no-division constraint: it leads to a cleaner, more general solution.

3. "What if you needed the maximum product instead of the product of all but one element?" This pivots to LeetCode 152 (Maximum Product Subarray), which requires tracking both a running maximum and running minimum at each step (because a negative minimum × a negative number flips to a large positive). It is a fundamentally different problem but uses similar left-to-right accumulation thinking.

4. "Can you extend this to a 2D matrix — product of everything in the matrix except the current cell?" Yes. You generalize to four passes: left-to-right by row, right-to-left by row, top-to-bottom by column, bottom-to-top by column. The same left × right principle applies, just extended into two dimensions.

5. "What is the product of the last k numbers in a stream?" This is LeetCode 1352. Maintain a running prefix-product array. To get the product of the last k numbers, divide the most recent prefix product by the prefix product from k positions back — unless a zero was encountered within the last k elements, in which case the answer is 0. This is one place where division is valid because the structure of the problem controls when zeros appear.

This Pattern Solves

Mastering the prefix/suffix accumulation pattern from this problem gives you a direct path to solving:

• LeetCode 42 — Trapping Rain Water (left max array + right max array)
• LeetCode 84 — Largest Rectangle in Histogram (left boundary + right boundary arrays)
• LeetCode 560 — Subarray Sum Equals K (prefix sum + hash map)
• LeetCode 1352 — Product of Last K Numbers (prefix product array on a stream)
• LeetCode 724 — Find Pivot Index (prefix sum from both ends)
• LeetCode 1480 — Running Sum of 1D Array (simple prefix accumulation)

The mental model is always the same: compute a cumulative property from the left, compute it from the right, combine.

Key Takeaway

LeetCode 238 is popular in top-tier interviews because it exposes how you think when the obvious path is cut off. The "no division" constraint forces you to decompose the problem into what every element "sees" on its left and on its right — a pattern that unlocks dozens of harder problems. Once you internalize that answer[i] = left_product[i] × right_product[i], and that the right product can be computed on the fly with a single variable instead of a full array, you have both a clean O(n)/O(n) solution and a polished O(n)/O(1) optimization ready to deliver under interview pressure.