Product of Array Except Self

The problem

Given a list of integers nums, return a list out where out[i] is the product of every element except nums[i]. Do it in O(n) time without using division.

The key insight

The product of everything except nums[i] is (product of everything to the left of i) times (product of everything to the right of i). Both are prefix-style running values, the multiplication version of prefix sums, so two passes give every answer.

Step-by-step approach

1. Create out of length n filled with 1.
2. Left pass: keep left = product of elements before i. Set out[i] = left, then multiply left by nums[i].
3. Right pass from the end: keep right = product of elements after i. Multiply out[i] by right, then multiply right by nums[i].
4. Return out; it now holds left-product times right-product at every index.

Python solution

def product_except_self(nums):
    n = len(nums)
    out = [1] * n
    left = 1
    for i in range(n):             # out[i] = product of nums[:i]
        out[i] = left
        left *= nums[i]
    right = 1
    for i in range(n - 1, -1, -1): # multiply in product of nums[i+1:]
        out[i] *= right
        right *= nums[i]
    return out

Complexity

Two linear passes. Apart from the output list, which the problem requires, only two running products are stored.

Common mistakes

• Using total product divided by nums[i], which crashes or gives wrong answers when the list contains a zero.
• Updating left before writing out[i], which includes nums[i] in its own product.
• Allocating separate prefix and suffix arrays is fine, but forgetting that the follow-up often asks for O(1) extra space.

Frequently asked questions

Related problems