Product of Array Except Self (LC 238)

Pattern: Prefix / suffix accumulation
Difficulty: Medium
Key Concept: answer[i] = (product of all elements to the left) × (product of all elements to the right); build prefix and suffix without using division.

Problem Statement

Given an integer array nums, return an array answer of the same length such that:

answer[i] = product of all elements of nums except nums[i].

Constraints (conceptual for this writeup): The product of any prefix or suffix of nums fits in a 32-bit integer. You must solve in O(n) time and without the division operator.

Input: Integer array nums.
Output: Integer array answer with the products described above.

---

1. Algorithm & Pseudocode

Brute force

1. Allocate answer of length n.
2. For each index i:
   • answer[i] = 1
   • For each j != i: answer[i] *= nums[j]
3. Return answer.

Optimal — two auxiliary arrays

1. Let n = nums.length.
2. prefix[i] = product of nums[0..i-1] (with prefix[0] = 1).
3. suffix[i] = product of nums[i+1..n-1] (with suffix[n-1] = 1).
4. answer[i] = prefix[i] * suffix[i].

Optimal — O(1) extra space (output does not count)

1. answer[i] first stores prefix product (product of elements left of i).
2. Second pass: multiply each answer[i] by a running suffix product from the right (variable suffix, starts at 1).

---

2. Step-by-Step Analysis (Beginner-Friendly)

• Why not divide? Division breaks when nums contains 0; the problem also forbids it. Prefix/suffix avoids that entirely.
• Why prefix × suffix? Everything except nums[i] is exactly “all to the left” times “all to the right” — nums[i] is the only element in neither group.
• O(1) extra space trick: The output array can hold prefix products first; then scan from the right with one int suffix variable to incorporate right-side products without a second full array.
• Overflow: Java int multiplication silently wraps on overflow (two’s complement), same conceptual pitfall as C++. For larger products, long intermediates are sometimes used in interviews; LeetCode 238 usually stays within 32-bit for the final answer.

---

3. The Dry Run

nums = [1, 2, 3, 4], n = 4.

Prefix products (product of elements strictly to the left of i):

i	left product	value
0	none	1
1	1	1
2	1×2	2
3	1×2×3	6

Suffix products (strictly to the right):

i	right product	value
0	2×3×4	24
1	3×4	12
2	4	4
3	none	1

answer[i] = prefix × suffix

i	nums[i]	prefix	suffix	answer[i]
0	1	1	24	24
1	2	1	12	12
2	3	2	4	8
3	4	6	1	6

Result: [24, 12, 8, 6].

O(1) extra space — after first pass answer holds prefix values: [1, 1, 2, 6].

Second pass (right to left; suffix accumulates product of elements to the right of i):

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

Final answer = [24, 12, 8, 6].

---

4. Java Solution

Brute Force

public int[] productExceptSelf(int[] nums) {
    int n = nums.length;
    int[] answer = 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];
            }
        }
        answer[i] = p;
    }
    return answer;
}

Time: O(n²).
Space: O(1) extra besides the required output array.

Optimal

Two-pass using output only (O(1) extra space)

public int[] productExceptSelf(int[] nums) {
    int n = nums.length;
    int[] answer = new int[n];

    answer[0] = 1;
    for (int i = 1; i < n; i++) {
        answer[i] = answer[i - 1] * nums[i - 1];
    }

    int suffix = 1;
    for (int i = n - 1; i >= 0; i--) {
        answer[i] *= suffix;
        suffix *= nums[i];
    }
    return answer;
}

Time: O(n).
Space: O(1) extra (the answer array is the required output).

Explicit prefix + suffix arrays (O(n) extra space, very clear)

public int[] productExceptSelf(int[] nums) {
    int n = nums.length;
    int[] prefix = new int[n];
    int[] suffix = new int[n];
    prefix[0] = 1;
    for (int i = 1; i < n; i++) {
        prefix[i] = prefix[i - 1] * nums[i - 1];
    }
    suffix[n - 1] = 1;
    for (int i = n - 2; i >= 0; i--) {
        suffix[i] = suffix[i + 1] * nums[i + 1];
    }
    int[] answer = new int[n];
    for (int i = 0; i < n; i++) {
        answer[i] = prefix[i] * suffix[i];
    }
    return answer;
}

---

5. The “Java vs. Others” Edge

• No division: Keeps the solution correct when zeros appear; Python one-liners with total / nums[i] fail on zero and violate the problem rules.
• Silent int overflow: Java does not throw on overflowing int multiply; neither does C++ for signed overflow (undefined behavior in C++ for signed overflow — another reason Java is more predictable here, though still wrong mathematically if overflow occurs). Consider long for intermediate products if constraints grow.
• long vs int: For learning, using long for suffix and prefix accumulators can avoid overflow in intermediate steps; the problem often guarantees final values fit in int.

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute Force	O(n²)	O(1) extra	Output array not counted toward extra space for comparison.
Optimal	O(n)	O(1) extra	Prefix in answer, then right-to-left suffix factor.
Optimal (explicit arrays)	O(n)	O(n) extra	Two helper arrays; easier to explain, more memory.