Product of Array Except Self

Product of Array Except Self is a classic "no division allowed" puzzle. It teaches the prefix/suffix product trick — sweep once from the left, once from the right, and combine.

The slow way first

The obvious idea: for each index i, loop over the whole array and multiply every element except nums[i]. That is two nested loops — O(n²) — far too slow for a large array.

The tempting shortcut is to multiply everything together once, then divide by nums[i]. But the problem bans division (and division breaks anyway when an element is 0). So we need a smarter structure.

The idea: split into left and right products

The product of everything except nums[i] equals:

(product of everything to the LEFT of i) × (product of everything to the RIGHT of i).

So if we knew, for every index, its left product and its right product, the answer is just one multiplication per cell. We compute those with two passes and reuse the output array to keep extra space at O(1).

The trick that makes it O(1) extra space: in the first pass we store each cell's left product directly in res. In the second pass we walk backward keeping a running right product suffix and multiply it into the value already sitting in res.

Walk through it

Step through the animation. In the prefix pass the pointer i moves left to right: each res[i] is set to prefix (the product so far), then prefix absorbs nums[i]. After that pass res = [1, 1, 2, 6] — each cell holds only its left product. Then the suffix pass walks i right to left with a running suffix: each res[i] is multiplied by suffix, then suffix absorbs nums[i]. The cells fill in to [24, 12, 8, 6].

Pseudocode

res = array of 1s, same length as nums
prefix = 1
for i from left to right:
    res[i] = prefix          # product of everything before i
    prefix = prefix * nums[i]
suffix = 1
for i from right to left:
    res[i] = res[i] * suffix  # fold in product of everything after i
    suffix = suffix * nums[i]
return res

The Python solution

def product_except_self(nums):
    n = len(nums)
    res = [1] * n
    prefix = 1
    for i in range(n):
        res[i] = prefix
        prefix *= nums[i]
    suffix = 1
    for i in range(n - 1, -1, -1):
        res[i] *= suffix
        suffix *= nums[i]
    return res

• res starts as all 1s and doubles as our output and scratch space.
• Prefix pass (lines 5-7): res[i] = prefix records the product of everything to the left, then prefix *= nums[i] extends it to include the current element for the next index.
• Suffix pass (lines 9-11): we walk backward, multiplying each res[i] by suffix (the product of everything to the right), then grow suffix by nums[i].
• Both prefix and suffix start at 1, the identity for multiplication, so the boundary cells (no left / no right neighbor) come out correct automatically.

Complexity

We use only two scalar accumulators beyond the output array, so the extra space is O(1) (the output array does not count). Two linear passes replace the O(n²) brute force.

When this pattern shows up

Practice