Product of Array Except Self

For each index, return the product of every other element, without division. The answer at i is (product of everything left of i) × (product of everything right of i): fill left products in one pass, then multiply in right products in a second pass.

Traced input: nums = [1, 2, 3, 4] → [24, 12, 8, 6]. Original problem: neetcode.io/problems/products-of-array-discluding-self

Complexity

Two passes. The output array doesn't count as extra space, and the suffix is one variable.

Key idea

• res[i] = prefix(i) × suffix(i), where neither includes nums[i].
• First pass: res[i] = res[i-1] × nums[i-1] stores prefix products.
• Second pass right-to-left: keep a running suffix and multiply it in.
• No division means zeros need no special handling.

Common mistakes

• Using division breaks on zeros, and the problem forbids it anyway.
• Off-by-one: the prefix for index 0 is 1 (empty product), not nums[0].
• Updating suffix before multiplying includes nums[i] in its own answer.

Solution

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

def productExceptSelf(nums: List[int]) -> List[int]:
    n = len(nums)
    res = [1] * n
    for i in range(1, n):
        res[i] = res[i - 1] * nums[i - 1]
    suffix = 1
    for i in range(n - 1, -1, -1):
        res[i] *= suffix
        suffix *= nums[i]
    return res

vector<int> productExceptSelf(vector<int>& nums) {
    int n = nums.size();
    vector<int> res(n, 1);
    for (int i = 1; i < n; i++) {
        res[i] = res[i - 1] * nums[i - 1];
    }
    int suffix = 1;
    for (int i = n - 1; i >= 0; i--) {
        res[i] *= suffix;
        suffix *= nums[i];
    }
    return res;
}

Edge cases

Each one has its own trace in the interactive view.