Product of Array Except Self

This problem looks like it has nothing to do with sums. It is here because the solution is two prefix scans — one from the left, one from the right — with multiplication in place of addition. It is one of the most frequently asked array problems at large companies, usually with the rule "no division" stated up front.

The rule is the whole difficulty. With division the problem is one line; without it, you need to see that a "prefix" does not have to be undone if you can build the answer from two sides.

The problem

Given a list of integers with at least two elements, return a new list where position i holds the product of every element except the one at i. You may not use division, and the solution should run in O(n) time.

• [2, 3, 4, 5] → [60, 40, 30, 24]. Position 0 is 3 × 4 × 5 = 60; position 2 is 2 × 3 × 5 = 30.
• [3, 0, 2, 5] → [0, 30, 0, 0]. Only position 1 skips the zero, so only it is non-zero: 3 × 2 × 5 = 30.

Constraints: 2 ≤ n ≤ 10⁵, values between −30 and 30, and every prefix and suffix product fits in a 32-bit integer.

Clarifying questions

• Is division allowed? No. (Ask anyway — it shows you know the easy route exists.)
• Can there be zeros? More than one? Yes, any number.
• Negative numbers? Yes; signs just multiply through.
• Does the output list count as extra space? Usually no. Then the best solution uses O(1) extra space.
• Overflow? Guaranteed not to happen here; in Java or C++ you would still note it.

Approach 1: the simple way

For each position, multiply every other element.

1def product_except_self_brute(nums: list[int]) -> list[int]:2    """For each index, multiply every other element."""3    n = len(nums)4    answer = []5    for i in range(n):6        product = 17        for j in range(n):8            if j != i:9                product *= nums[j]10        answer.append(product)11    return answer

Time is O(n²): n positions, each multiplying n − 1 numbers. Space is O(1) beyond the output.

Why it is too slow: at n = 10⁵ that is about 10¹⁰ multiplications — many minutes in Python. The waste is the same as in range-sum queries. The products for position 3 and position 4 share n − 2 factors, and the loop recomputes all of them.

Why not divide? Multiply everything once and divide by nums[i]. It is O(n), but it breaks on zero: with [3, 0, 2, 5] the total is 0, and 0 / 0 is undefined. You can repair it by counting zeros (no zeros: divide; one zero: only that position is non-zero; two or more: all zeros), but the problem bans division precisely to push you past this.

The key insight

Look at what "everything except i" means on the line of numbers:

[ nums[0] ... nums[i-1] ]   nums[i]   [ nums[i+1] ... nums[n-1] ]      left of i             skipped          right of i

The product you want is (product of everything left of i) × (product of everything right of i). Nothing needs removing, so nothing needs dividing.

"Product of everything left of i" is a prefix product, and every one of them comes from the previous one with one multiplication: left[i] = left[i − 1] × nums[i − 1]. "Product of everything right of i" is the same thing scanned from the other end. Two O(n) passes build both.

This is why prefix sums need an inverse but this problem does not. A range sum removes the unwanted head by subtracting. Here we never remove anything; we combine two pieces that were never together.

A zero is handled for free. If nums[3] = 0, every left[i] for i > 3 is 0 and every right[i] for i < 3 is 0. Only position 3 multiplies two zero-free pieces.

Approach 2: two helper arrays

1def product_except_self_two_arrays(nums: list[int]) -> list[int]:2    """answer[i] = (product left of i) * (product right of i)."""3    n = len(nums)4    left = [1] * n                    # left[i] = nums[0] * ... * nums[i-1]5    for i in range(1, n):6        left[i] = left[i - 1] * nums[i - 1]7    right = [1] * n                   # right[i] = nums[i+1] * ... * nums[n-1]8    for i in range(n - 2, -1, -1):9        right[i] = right[i + 1] * nums[i + 1]10    return [left[i] * right[i] for i in range(n)]

For [2, 3, 4, 5]: left = [1, 2, 6, 24], right = [60, 20, 5, 1], and the pairwise products are [60, 40, 30, 24]. The empty product is 1 — the same role the leading zero plays for sums.

Time is O(n) (three passes), and extra space is O(n) for left and right.

Approach 3: one running variable

The output array can hold the left products, and the right products can live in one variable that grows as we walk backwards.

1. Pass 1, left to right: write the product of everything before i into answer[i], then multiply nums[i] into the running product.
2. Pass 2, right to left: multiply answer[i] by the running product of everything after i, then multiply nums[i] in.

1def product_except_self(nums: list[int]) -> list[int]:2    """Same idea, with the right products kept in one running variable."""3    n = len(nums)4    answer = [1] * n5    running = 16    for i in range(n):                # pass 1: answer[i] = product left of i7        answer[i] = running8        running *= nums[i]9    running = 110    for i in range(n - 1, -1, -1):    # pass 2: multiply in product right of i11        answer[i] *= running12        running *= nums[i]13    return answer

Dry run on [2, 3, 4, 5]

Pass 1 (left to right):

Pass 2 (right to left):

The result matches the expected output. Check index 2 by hand: 2 × 3 × 5 = 30.

Complexity. Time is O(n): two passes, one multiplication each per element. Extra space is O(1) — just running — because the output array does not count. If the interviewer does count it, say so: the answer must be returned anyway, so O(n) output is unavoidable.

Edge cases

• One zero. [3, 0, 2, 5] → [0, 30, 0, 0]. Every position except the zero picks up the zero from one side.
• Two or more zeros. [0, 4, 0] → [0, 0, 0]. Every position still has a zero on at least one side.
• Negative numbers. [-1, 2] → [2, -1]. Signs multiply through without special handling.
• n = 2. Each position gets the other element. The loops handle it: pass 1 gives [1, nums[0]], pass 2 multiplies in [nums[1], 1].
• All ones. Every answer is 1. A quick sanity test for the empty-product seeds.

Saying it in the interview

Follow-ups

• "Now division is allowed." Count zeros. None: total product ÷ nums[i]. Exactly one: only the zero's position gets the product of the others; the rest are 0. Two or more: all 0. Still O(n).
• "Answer many queries: product of the range i..j." Prefix products fail on zero (you cannot divide it back out). Keep a prefix count of zeros plus prefix products of the non-zero values, or use a segment tree for O(log n) per query.
• "Maximum product of any subarray." Different problem: track the largest and smallest product ending at each index, because a negative can turn the smallest into the largest. That is dynamic programming, not prefix products.