Product of Array Except Self (LC 238)

Pattern: Prefix × Suffix Products (No Division) Difficulty: Medium Key Concept: For each index i, answer[i] = (product of everything to the left) * (product of everything to the right). Build these two passes in O(n) and combine.

Problem Statement

Given an integer array nums, return an array answer such that answer[i] equals the product of all elements of nums except nums[i].

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

Example

• nums = [1, 2, 3, 4] → [24, 12, 8, 6]
• nums = [-1, 1, 0, -3, 3] → [0, 0, 9, 0, 0]

---

1. Algorithm & Pseudocode

Brute force

For each i, multiply everything except nums[i] — (O(n^2)).

“Cheater” with division

Compute total product, then answer[i] = total / nums[i]. Fails on zeros and is disallowed.

Optimal — Prefix × Suffix

1. Create int[] answer of size n.
2. First pass (left → right): answer[i] = product of nums[0..i-1]. Use a running prefix.
3. Second pass (right → left): multiply answer[i] *= product of nums[i+1..n-1]. Use a running suffix.

This uses O(1) extra space (the output array doesn’t count).

---

2. Step-by-Step Analysis

Why prefix × suffix works Every element of the array except nums[i] lies either left of i or right of i. So answer[i] = prefix[i] * suffix[i], where:

• prefix[i] = nums[0] * nums[1] * ... * nums[i-1] (= 1 for i=0)
• suffix[i] = nums[i+1] * nums[i+2] * ... * nums[n-1] (= 1 for i=n-1)

Why we can reuse the output array Instead of allocating both prefix[] and suffix[], we:

1. Fill answer[i] with the prefix on the first pass.
2. Multiply in the suffix on the second pass using a single rolling variable.

That cuts space from O(n) auxiliary down to O(1).

Why no division is required The two-pass trick captures the product of left and right halves without ever needing total / nums[i].

ASCII Trace for [1, 2, 3, 4]

First pass (left → right), prefix starts at 1:
i=0  answer[0]=prefix=1   then prefix *= nums[0]=1   → prefix=1
i=1  answer[1]=prefix=1   then prefix *= nums[1]=2   → prefix=2
i=2  answer[2]=prefix=2   then prefix *= nums[2]=3   → prefix=6
i=3  answer[3]=prefix=6   then prefix *= nums[3]=4   → prefix=24

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

Second pass (right → left), suffix starts at 1:
i=3  answer[3] *= suffix=1  → answer[3] = 6;   suffix *= nums[3]=4   → suffix=4
i=2  answer[2] *= suffix=4  → answer[2] = 8;   suffix *= nums[2]=3   → suffix=12
i=1  answer[1] *= suffix=12 → answer[1] = 12;  suffix *= nums[1]=2   → suffix=24
i=0  answer[0] *= suffix=24 → answer[0] = 24

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

---

3. The Dry Run

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

Pass 1 (prefix):

i	prefix (before)	answer[i]	After: prefix *= nums[i]
0	1	1	1
1	1	1	2
2	2	2	6
3	6	6	24

Pass 2 (suffix):

i	suffix (before)	answer[i] *= suffix	After: suffix *= nums[i]
3	1	6	4
2	4	8	12
1	12	12	24
0	24	24	24

Return [24, 12, 8, 6].

---

4. Java Solution

Brute Force

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            int p = 1;
            for (int j = 0; j < n; j++) if (j != i) p *= nums[j];
            ans[i] = p;
        }
        return ans;
    }
}

Time: (O(n^2)) Space: (O(1)) extra

Optimal

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];

        // Pass 1: ans[i] = product of nums[0..i-1]
        int prefix = 1;
        for (int i = 0; i < n; i++) {
            ans[i] = prefix;
            prefix *= nums[i];
        }

        // Pass 2: multiply by product of nums[i+1..n-1]
        int suffix = 1;
        for (int i = n - 1; i >= 0; i--) {
            ans[i] *= suffix;
            suffix *= nums[i];
        }
        return ans;
    }
}

Time: (O(n)) Space: (O(1)) extra (output excluded by problem rules)

---

5. The “Java vs. Others” Edge

• Java int[] is zero-initialized on allocation, but here we always overwrite, so we initialize prefix = 1 instead.
• Watch overflow: per LC constraints, products fit in int. If they didn’t, use long.
• Could compute with long[] and cast at the end if input range expanded.

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute Force	(O(n^2))	(O(1))	Two nested loops.
Optimal	(O(n))	(O(1))	Two passes, output array as scratch.