Product of Array Except Self (LeetCode 238)

The problem

Given an integer array nums, return an array res where res[i] is the product of every element except nums[i]. You may not use division, and the solution should run in O(n).

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

For example res[1] = 1 × 3 × 4 = 12: everything except the 2.

How to think about it

Start with brute force. For each index, multiply all the other elements. That is O(n²). The obvious shortcut, multiply everything once and divide by nums[i], is banned, and it also breaks the moment a zero appears.

The key insight: “everything except i” is “everything left of i” times “everything right of i“. Call them the prefix product and the suffix product. Both can be built in a single pass each: walking left to right, the prefix product for i is the product of everything already passed. Walking right to left, the same holds for the suffix.

Save space by reusing the output. First pass: write the prefix product into res[i], then fold nums[i] into the running pre. Second pass, from the right: multiply res[i] by the running post, then fold nums[i] into post. Each running value is a single number, so beyond the output array you use O(1) extra space.

Which pattern is this? Prefix sums, with multiplication instead of addition. The tell is “combine everything except the current element”: split it into a left part and a right part.

Approach

1. Create res = [1] * n and set pre = 1.
2. Left to right: set res[i] = pre, then pre *= nums[i]. Now res[i] is the product of nums[0..i-1].
3. Set post = 1.
4. Right to left: res[i] *= post, then post *= nums[i]. Now res[i] also includes nums[i+1..n-1].
5. Return res.

Solution

def product_except_self(nums):
    n = len(nums); res = [1]*n
    pre = 1
    for i in range(n):
        res[i] = pre; pre *= nums[i]     # res[i] = product of everything to the left
    post = 1
    for i in range(n-1, -1, -1):
        res[i] *= post; post *= nums[i]  # multiply in everything to the right
    return res
# product_except_self([1,2,3,4]) -> [24,12,8,6]

Dry run

nums = [1, 2, 3, 4]. Values shown after each step.

The final res is [24, 12, 8, 6].

Complexity

• Time: O(n). Two linear passes.
• Space: O(1) extra. Only pre and post; the output array does not count, as the problem states.

Edge cases and pitfalls

• One zero in the input: every position except the zero’s own gets 0, and the zero’s position gets the product of the rest. The two-pass method handles this with no special case: [0, 2, 3] gives [6, 0, 0].
• Two or more zeros: every answer is 0, again with no special case.
• The division trick fails on zeros and is disallowed anyway; do not reach for it.
• Order inside each loop matters. Write res[i] before multiplying nums[i] into the running product, or you include the element itself.
• Overflow is not a concern in Python, but in Java or C++ the problem guarantees the products fit in 32 bits.

Related problems

• Find Pivot Index (LeetCode 724): the same left-side versus right-side split, with sums.
• Trapping Rain Water (LeetCode 42): also built from a prefix max and a suffix max at each index.
• Product of the Last K Numbers (LeetCode 1352): prefix products answering queries, with zeros handled carefully.