Product of Array Except Self

Problem

Given an integer array nums, return an array output where output[i] is the product of all the elements of nums except nums[i]. Each product is guaranteed to fit in a 32-bit integer.

Follow-up: Could you solve it in $O(n)$ time without using the division operation?

Example 1

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

Example 2

Input:  nums = [-1, 0, 1, 2, 3]
Output: [0, -6, 0, 0, 0]

Constraints

• 2 <= len(nums) <= 10^5
• -30 <= nums[i] <= 30
• The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

Thinking

• Brute force idea: for each i, multiply every other element: $O(n^2)$. Too slow at $n = 10^5$.
• Division idea: total product $P$, then output[i] = P / nums[i]: $O(n)$. But it breaks on zeros (need special cases for 0, 1, or 2+ zeros), and the follow-up forbids division.
• Key insight: “everything except i” = everything to the left of i × everything to the right of i: $\text{output}[i] = \underbrace{\textstyle\prod_{j<i} \text{nums}[j]}_{\text{prefix}} \times \underbrace{\textstyle\prod_{j>i} \text{nums}[j]}_{\text{suffix}}$ Both are running products, so one left-to-right pass and one right-to-left pass give every answer in $O(n)$ with no division. Zeros need no special handling.
• Space trick: store the prefix products directly in output, then sweep right-to-left multiplying in a single running suffix variable → $O(1)$ extra space (the output array doesn’t count).
• Edge cases to remember: one zero (only its own position is non-zero), two or more zeros (everything is 0), negative numbers, length 2 ([a, b] → [b, a]).

Walkthrough of the best solution (Approach C)

The idea: for position i, “everything except nums[i]” splits into two parts:

nums = [ a, b, c, d, e ]
               ↑ i = 2
everything except c  =  (a × b)   ×   (d × e)
                         left part    right part
                         = prefix     = suffix

By hand, for nums = [1, 2, 4, 6] (“nothing” counts as 1, which is why prefix and suffix both start at 1):

Pass 1, left to right: store the prefix product in result.

prefix = 1
for i in range(n):
    result[i] = prefix     # ① store "product of everything LEFT of i"
    prefix *= nums[i]      # ② then include nums[i] for the next position

The order of ① and ② is the key detail: store first, multiply after. When result[i] is written, prefix doesn’t include nums[i] yet, so position i is left out. Swap the lines and every position includes itself.

Pass 2, right to left: multiply in the suffix product, kept in one running variable.

suffix = 1
for i in range(n - 1, -1, -1):
    result[i] *= suffix    # ① result[i] = prefix × "product RIGHT of i"
    suffix *= nums[i]      # ② then include nums[i] for the next position (to the left)

Why one variable instead of a suffix array? Each suffix value is used once, exactly when the right-to-left pass reaches that position, so a running variable is enough. The only array is result (the output doesn’t count), so extra space is $O(1)$.

Why zeros need no special case, for nums = [-1, 0, 1, 2, 3]:

• Pass 1 gives result = [1, -1, 0, 0, 0]. Once prefix passes the 0, it stays 0.
• Pass 2, right to left:
  • i=4: 0 × 1 = 0, then suffix = 3
  • i=3: 0 × 3 = 0, then suffix = 6
  • i=2: 0 × 6 = 0, then suffix = 6
  • i=1: −1 × 6 = −6, then suffix = 0
  • i=0: 1 × 0 = 0
• Result [0, -6, 0, 0, 0] ✓. The zero’s own position skips the zero on both sides, so it gets the real product. Every other position picks up the zero from one side. Nothing is divided, so nothing special is needed.

Summary: answer = left product × right product. In each pass, use the running product, then multiply in nums[i]. That order is what leaves nums[i] out.

Solution

Approach A — my version (total product + division, zero counting)

Complexity: Time $O(n)$ · Space $O(1)$ extra. It’s correct and the Big-O is already optimal, but it doesn’t answer the question being asked:

1. It uses division, which the follow-up rules out. Division is also the fragile part: it needs the three zero cases (0, 1, 2+ zeros), and // only works because the division is always exact (// floors, so a non-exact case with negatives would be wrong). In C++/Java the full product can also overflow even when every answer fits.
2. Several passes: nums.count(0), math.prod(nums), then the division pass; in the one-zero case it adds an enumerate pass plus a filtered copy of the list. They’re mostly C-level loops, so it’s still quick in Python.
3. Small things: result is built before the early return even when unused; prod != 0 is just zero_count == 0 again; the comprehension reuses the name num from the outer loop.

The code is unchanged except for the signature and comments.

import math
from itertools import accumulate
from operator import mul

def product_except_self_mine(nums: list[int]) -> list[int]:
    zero_count = nums.count(0)                       # pass 1
    result = [0 for _ in range(len(nums))]
    if zero_count > 1:
        return result
    prod = math.prod(nums)                           # pass 2

    if prod != 0:                                    # same as zero_count == 0
        return [prod // num for num in nums]         # DIVISION: what the follow-up forbids
    for index, num in enumerate(nums):               # pass 3 (one-zero case only)
        if num == 0:
            new_prod = math.prod([num for num in nums if num != 0])  # copies the list
            result[index] = new_prod
    return result

Approach B — prefix and suffix arrays

Complexity: Time $O(n)$ · Space $O(n)$ extra. prefix[i] = product of everything left of i, suffix[i] = product of everything right of i; the answer is prefix[i] * suffix[i]. The easiest version to derive on a whiteboard: write it first, then optimise the space away (Approach C).

def product_except_self_arrays(nums: list[int]) -> list[int]:
    n = len(nums)
    prefix = [1] * n
    suffix = [1] * n
    for i in range(1, n):
        prefix[i] = prefix[i - 1] * nums[i - 1]
    for i in range(n - 2, -1, -1):
        suffix[i] = suffix[i + 1] * nums[i + 1]
    return [p * s for p, s in zip(prefix, suffix)]

Approach C — prefix in the output, running suffix ✅ best practice (interview answer)

Complexity: Time $O(n)$ · Space $O(1)$ extra (output not counted). Pass 1 writes the prefix products into result. Pass 2 walks right-to-left keeping the suffix product in one variable and multiplies it in. No division, no zero cases, two passes.

def product_except_self(nums: list[int]) -> list[int]:
    n = len(nums)
    result = [1] * n
    prefix = 1
    for i in range(n):
        result[i] = prefix          # product of nums[:i]
        prefix *= nums[i]
    suffix = 1
    for i in range(n - 1, -1, -1):
        result[i] *= suffix         # times product of nums[i+1:]
        suffix *= nums[i]
    return result

Approach D — itertools.accumulate (Pythonic)

Complexity: Time $O(n)$ · Space $O(n)$ extra. Same prefix × suffix idea, but the running products are computed in C by accumulate. initial=1 shifts them by one so prefix[i] excludes nums[i]. Short, but it uses $O(n)$ extra space and wasn’t faster than C in the timing below. Good to know accumulate; in an interview, write C.

def product_except_self_accumulate(nums: list[int]) -> list[int]:
    prefix = list(accumulate(nums, mul, initial=1))            # prefix[i] = prod(nums[:i])
    suffix = list(accumulate(reversed(nums), mul, initial=1))  # suffix[j] = prod of last j
    # output[i] = prefix[i] * suffix[n-1-i]; map/zip stop at the shorter, all in C
    return list(map(mul, prefix, reversed(suffix[:-1])))

Scratch / Experiments

Max size $n = 10^5$. Random values would make the product astronomically large (Python ints never overflow, so it would measure bigint arithmetic), so to respect the “fits in 32 bits” constraint the input is mostly $\pm 1$ with a few $2$s. Two inputs: no zeros, and one zero (the extra-pass branch of Approach A).

Typical results (ms, $n = 10^5$):

All four are $O(n)$, so the gaps are constant factors:

• A is fastest with no zeros because count, math.prod and one comprehension are mostly C-level work. With one zero it does extra passes and C catches up. Fast, but it skips the follow-up, which was the point.
• B is slowest: two extra $n$-sized lists plus three Python loops (two index loops and the zip). C does the same work with no extra arrays.
• D isn’t a free win: accumulate/map run in C, but it builds three $n$-sized lists (prefix, suffix, the suffix[:-1] slice) and every multiplication still creates a Python int, so it ends up level with C. “Use the C builtin” only pays off when it removes a lot of Python bytecode; here C’s loop is already very simple.

import random

random.seed(0)
no_zero = [random.choice([1, -1]) for _ in range(100_000)]
for i in random.sample(range(100_000), 20):
    no_zero[i] = 2
one_zero = list(no_zero)
one_zero[50_000] = 0

for label, nums in [("no zero", no_zero), ("one zero", one_zero)]:
    print(f"--- {label}")
    for fn in APPROACHES:
        print(f"{fn.__name__:32s}", end=" ")
        %timeit fn(nums)

Takeaways

• Pattern: “combine everything except index i” (or “everything left of i” / “everything right of i”) → prefix × suffix: one pass left-to-right, one pass right-to-left. Store one direction in the output and keep the other as a running variable for $O(1)$ extra space. Same shape as prefix sums, just with * instead of +.
• Mistakes I made:
  • Reached for division to “undo” one element. Inverting an operation needs special cases (here: zeros, and exact vs floor division with negatives) and is often banned or impossible (max, gcd, overflow in fixed-width ints). Prefix/suffix needs no inverse at all.
  • Didn’t treat the follow-up as the real question: ”$O(n)$ without division” was the point of the problem.
  • Small hygiene: built result before an early return that didn’t need it, checked the same condition twice (zero_count and prod != 0), and reused num inside a comprehension.
• Related problems: Range Sum Query – Immutable (#303, prefix sums), Trapping Rain Water (#42, prefix max from the left vs suffix max from the right), Maximum Product Subarray (#152, running products with negatives), Subarray Sum Equals K (#560, prefix sums + hash map), Find Pivot Index (#724, left sum vs right sum).