Product of Array Except Self: Prefix and Suffix Products in O(n)

Product of array except self looks like a warm-up: multiply everything, then divide by each value. The problem statement usually forbids division, and even when it does not, a single zero breaks that shortcut. The intended answer is two sweeps over the array and two running products, and it is worth knowing well because the same left-and-right idea comes back in trapping rain water, candy distribution and many other array problems.

The problem it solves

Given an array nums, return an array out where out[i] is the product of every value except nums[i]. For [2, 3, 4, 5] the answer is [60, 40, 30, 24]: 60 is 3 × 4 × 5, 40 is 2 × 4 × 5, and so on. The usual constraints are "no division" and "O(n) time", and the follow-up asks for O(1) extra space, not counting the output.

The brute force multiplies n - 1 values for each of n positions, which is O(n^2).

The intuition

Split the product at i into two halves: everything to the left of i, and everything to the right. Neither half contains nums[i], so their product is exactly the answer.

Both halves can be built incrementally:

• Left to right, keep a running prefix. At each i, write prefix into out[i] first, and only then multiply nums[i] into it. The order is the whole trick: the value at i is folded in after it is used, so out[i] never includes itself.
• Right to left, keep a running suffix and do the same thing, but multiply it into out[i] instead of overwriting.

After the first sweep, out[i] holds the left product. After the second, it holds left times right. The output array doubles as the storage for the prefix products, which is why the extra space is just two variables.

This is the multiplicative cousin of prefix sums. With sums you would subtract to get "everything except i"; with products you cannot divide safely, so you keep the two sides apart instead.

Watch it run

The animation uses [2, 3, 4, 5]. On the way right it writes 1, 2, 6 and 24 into the output, each time before folding the current value in. On the way back, out[3] becomes 24 × 1, then out[2] becomes 6 × 5 = 30, out[1] becomes 2 × 20 = 40, and out[0] becomes 1 × 60 = 60. No cell ever meets its own value.

The code

The two sweeps, with zeros and negatives:

def product_except_self(nums):
    out = [1] * len(nums)
    prefix = 1
    for i in range(len(nums)):                # left to right
        out[i] = prefix                       # everything left of i
        prefix *= nums[i]                     # only now fold nums[i] in
    suffix = 1
    for i in range(len(nums) - 1, -1, -1):    # right to left
        out[i] *= suffix                      # times everything right of i
        suffix *= nums[i]
    return out

print(product_except_self([2, 3, 4, 5]))       # [60, 40, 30, 24]
print(product_except_self([1, 2, 0, 4]))       # [0, 0, 8, 0]
print(product_except_self([-1, 1, 0, -3, 3]))  # [0, 0, 9, 0, 0]
print(product_except_self([7]))                # [1]

Why division is a trap: the total is 0 as soon as the array holds a zero, and dividing by that zero crashes. A division version can be rescued by counting zeros, which is a fair follow-up question:

def divide_naive(nums):
    total = 1
    for x in nums:
        total *= x
    return [total // x for x in nums]

try:
    divide_naive([1, 2, 0, 4])
except ZeroDivisionError as e:
    print("ZeroDivisionError:", e)             # ZeroDivisionError: integer division or modulo by zero

def divide_with_zero_count(nums):
    zeros = nums.count(0)
    rest = 1
    for x in nums:
        if x != 0:
            rest *= x                          # product of the non-zero values
    if zeros > 1:
        return [0] * len(nums)
    if zeros == 1:
        return [rest if x == 0 else 0 for x in nums]
    return [rest // x for x in nums]

print(divide_with_zero_count([1, 2, 0, 4]))    # [0, 0, 8, 0]

Both against a brute force on 2,000 random arrays full of zeros and negative numbers:

import random

def brute(nums):
    out = []
    for i in range(len(nums)):
        p = 1
        for j, x in enumerate(nums):
            if j != i:
                p *= x
        out.append(p)
    return out

random.seed(16)
ok = True
for _ in range(2000):
    nums = [random.randint(-4, 4) for _ in range(random.randint(1, 9))]
    want = brute(nums)
    ok &= product_except_self(nums) == want == divide_with_zero_count(nums)
print(ok)                                      # True

The complexity

• Brute force: O(n^2) time, O(1) extra space.
• Two sweeps: each index is visited twice, so O(n) time. The extra space is O(1), the two running products, because the output array holds the prefix products. If an interviewer counts the output, it is O(n), and you should say which convention you are using.
• Two separate arrays: a common first version builds a full left array and a full right array, then multiplies them. That is also O(n) time, with O(n) extra space. It is a fine stepping stone; the one-array version is the finished answer.

Where it goes wrong

• Folding in before writing. Swap the two lines in the first loop and out[i] includes nums[i]. The animation's order, write then multiply, is the fix.
• Overwriting on the way back. The second sweep must multiply into out[i]; assigning suffix to it throws the left half away.
• Assuming no zeros. One zero makes every other answer 0; two zeros make every answer 0. The sweeps handle both without a special case.
• Overflow in other languages. Python integers do not overflow. In Java or C++ the problem usually guarantees that every prefix and suffix product fits in 32 bits; if not, use a 64-bit type and say why.

When it shows up in interviews

It shows up as an early medium question, and it tests whether you can find a linear solution under an explicit constraint rather than reach for the obvious one. The "no division" rule is the tell that the interviewer wants the prefix and suffix idea. Two follow-ups are common: "now do it in O(1) extra space", which the one-array version already answers, and "what if division were allowed?", which the zero-counting version answers. Outside interviews, the same shape turns up whenever each item needs an aggregate of all the others, like the combined yield of every stage but one on a production line.

How to say it in an interview

"The answer at i is the product of everything left of i times everything right of i. I sweep left to right with a running prefix product, writing it into out[i] before I multiply nums[i] in, so out[i] holds the left product. Then I sweep right to left with a running suffix product and multiply it in. That is O(n) time and O(1) extra space besides the output, and zeros need no special handling because I never divide."

Prefix products are the product version of prefix sums, and prefix sums explained visually covers the additive version and its range queries.