Product of Array Except Self

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 O(n) algorithm without using division.

Example 1:

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

Example 2:

Input: nums = [-1, 1, 0, -3, 3]
Output: [0, 0, 9, 0, 0]
Explanation: Only index 2 (the 0) excludes a non-zero product; others include the 0.

Constraints:

• 2 <= nums.length <= 10^5.
• -30 <= nums[i] <= 30.
• The product of any prefix/suffix fits in a 32-bit integer.

Difficulty: Medium LC: 238 Round: Technical R1

---

Pattern Recognition

• What is the input structure? A flat integer array.
• What are we optimizing? Linear time, no division, constant extra space (output doesn't count).
• What pattern does this fit? Prefix / suffix products.
• Why does this pattern fit? answer[i] = (product of nums[0..i-1]) * (product of nums[i+1..n-1]). Compute prefix in one pass, fold in suffix in a second pass.

---

Approach

Brute Force — Multiply Every Other Element

For each i, multiply all other elements.

Time: O(n^2). Space: O(1). Why insufficient: 10^10 ops for n = 10^5.

Forbidden — Division

Compute the total product, then answer[i] = total / nums[i]. Disallowed by the problem and fails on zeros.

Optimal — Prefix/Suffix in Two Passes

Key Insight: answer[i] is the product of all elements to the left of i times the product of all elements to the right of i. You compute these in two sweeps, reusing the output array to hold prefix products on the way down and multiplying in suffix products on the way up.

Step-by-step:

1. Initialize answer of size n, all 1s.
2. Left-to-right pass: maintain prefix = 1. For each i, set answer[i] = prefix, then prefix *= nums[i].
3. Right-to-left pass: maintain suffix = 1. For each i from n-1 down to 0, set answer[i] *= suffix, then suffix *= nums[i].
4. Return answer.

After step 2, answer[i] = product of nums[0..i-1]. After step 3, each answer[i] is multiplied by product of nums[i+1..n-1].

Time: O(n) total (two passes). Space: O(1) extra (the output array is not counted per problem statement).

---

Walkthrough

Trace on nums = [1, 2, 3, 4]:

Left pass: prefix = 1, answer = [1, 1, 1, 1].

i	answer[i] before	set answer[i] = prefix	prefix after
0	1	1	1 * 1 = 1
1	1	1	1 * 2 = 2
2	1	2	2 * 3 = 6
3	1	6	6 * 4 = 24

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

Right pass: suffix = 1.

i	answer[i] before	answer[i] *= suffix	suffix after
3	6	6 * 1 = 6	1 * 4 = 4
2	2	2 * 4 = 8	4 * 3 = 12
1	1	1 * 12 = 12	12 * 2 = 24
0	1	1 * 24 = 24	24 * 1 = 24

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

---

Implementation

TypeScript

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

    // Left pass: answer[i] = product of nums[0..i-1].
    let prefix = 1;
    for (let i = 0; i < n; i++) {
        answer[i] = prefix;
        prefix *= nums[i];
    }

    // Right pass: fold in the suffix products.
    let suffix = 1;
    for (let i = n - 1; i >= 0; i--) {
        answer[i] *= suffix;
        suffix *= nums[i];
    }
    return answer;
}

C++

#include <vector>

std::vector<int> productExceptSelf(std::vector<int>& nums) {
    int n = nums.size();
    std::vector<int> answer(n, 1);

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

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

Watch out:

1. Using division. The problem forbids it and division fails on zeros anyway.
2. Overflow. Products can exceed int32 for many small factors. Use long long in C++ or BigInt if constraints allow.
3. Handling zeros. The two-pass approach handles zeros naturally. No special case needed. If there is exactly one zero, only that index gets a non-zero product; otherwise all outputs are zero.

---

Complexity Analysis

	Time	Space
Brute Force	O(n^2)	O(1)
Optimal (Prefix/Suffix)	O(n)	O(1) extra

Bottleneck: Two linear passes, unavoidable.

---

Edge Cases

1. Single zero in array — output has a non-zero value only at that index.
2. Multiple zeros — all outputs are zero.
3. All ones — output is all ones.
4. Mix of positive and negative — sign combinatorics handled by the standard multiplication.
5. Array of length 2 — answer = [nums[1], nums[0]].

---

Related Problems

• LC 152 — Maximum Product Subarray — Prefix/suffix products but with max constraint.
• LC 42 — Trapping Rain Water — Same prefix/suffix idea on max-heights.
• LC 724 — Find Pivot Index — Prefix sums variant.
• LC 1769 — Minimum Number of Operations to Move All Balls to Each Box — Prefix/suffix on counts.

---

Interview Strategy Notes

Common Salesforce Technical R1 problem. Expect 10-15 minutes. The interviewer may push on "can you do it in O(1) extra space?" — the answer is yes: the output array doesn't count, and you can merge the two passes mentally (though not structurally) into one thought.

---

What is Expected at Each Level

Junior: Tries division, gets stopped. Arrives at prefix/suffix with a hint. Writes the two-pass solution.

Mid-level: Prefix/suffix immediately. Discusses the zero-handling elegance. Explains why the output array isn't counted in the "O(1) extra space" claim.

Senior: Writes the two-pass solution in one go. Discusses overflow, mentions the generalization to modular arithmetic (where division is fine given a prime modulus and modular inverse). Extends to the related LC 152.