Product of Array Except Self

What the problem is really asking

For each index, we need the product of every number except the one at that index.

The catch is that the usual shortcut, division, is not allowed.

Intuition

For any position i, the answer is:

• product of everything on the left
• multiplied by product of everything on the right

So if we can get left-product and right-product efficiently, we are done.

Brute-force idea

The slow solution is:

• for each index
• multiply every other element

That works, but it takes O(n^2) time.

Optimized approach

We build the answer in two passes.

Pass 1: left products

Store in answer[i] the product of all elements before index i.

Pass 2: right products

Walk from right to left with a running suffix product.

Multiply answer[i] by suffix, then update suffix *= nums[i].

That way each position gets both sides without extra arrays.

class Solution {
    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;
    }
}

Dry run

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

After the left pass:

answer = [1, 1, 2, 6]

Now walk from the right:

• suffix = 1, index 3 -> answer[3] = 6
• suffix = 4, index 2 -> answer[2] = 2 * 4 = 8
• suffix = 12, index 1 -> answer[1] = 1 * 12 = 12
• suffix = 24, index 0 -> answer[0] = 1 * 24 = 24

Final answer:

[24, 12, 8, 6]

Common mistakes

1. Trying to use division

That breaks the rule of the problem and also becomes messy when zeros exist.

2. Forgetting that the answer array can store the prefix products

You do not need a full extra left array and right array.

3. Updating suffix in the wrong order

You must multiply answer[i] by the current suffix first, then extend suffix with nums[i].

Complexity

Time Complexity: O(n)

Space Complexity: O(1) extra, if the output array does not count