Product of Array Except Self

Interview Prep

Warm-upArrays & Hashingarraysprefix-products

The problem

Given an integer array nums, return an array out where out[i] equals the product of all elements except nums[i]. Solve it in O(n) and without using division (the obvious "compute total product, divide" trick is forbidden — and would break for zeros anyway).

Pattern: prefix and suffix products

"Product of all other elements" decomposes naturally into "product of everything to the left" times "product of everything to the right." Each side is a running product over the array. Two passes, no division.

Brute force

def product_except_self(nums: list[int]) -> list[int]:
    n = len(nums)
    out = [1] * n
    for i in range(n):
        for j in range(n):
            if j != i:
                out[i] *= nums[j]
    return out

O(n²) time, O(n) space (just the output). Quadratic because of the nested loop.

Solution 2 — prefix & suffix arrays

def product_except_self(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 [prefix[i] * suffix[i] for i in range(n)]

O(n) time, O(n) space (two extra arrays). Clean and obvious. The only weakness is the auxiliary memory.

Solution 3 — O(1) extra space

def product_except_self(nums: list[int]) -> list[int]:
    n = len(nums)
    out = [1] * n

    # First pass: out[i] = product of everything to the LEFT of i.
    left = 1
    for i in range(n):
        out[i] = left
        left *= nums[i]

    # Second pass: multiply in the product of everything to the RIGHT of i.
    right = 1
    for i in range(n - 1, -1, -1):
        out[i] *= right
        right *= nums[i]

    return out

O(n) time, O(1) extra space. Use the output array itself as the prefix accumulator, then sweep right-to-left multiplying in the suffix on the fly. Two passes, two scalars, no auxiliary arrays. This is the version interviewers want.

Walkthrough

nums   = [1, 2, 3, 4]
left   = 1, 1, 2, 6        (after first pass, out = [1, 1, 2, 6])
right  = 24, 12, 4, 1      (carried implicitly during second pass)
out    = [24, 12, 8, 6]

Edge cases

Related