Problem 4 · Arrays & Hashing

Product of Array Except Self

MediumClassic DSA & systems

01Problem

Return an array where output[i] is the product of all elements of nums except nums[i], without using division, in O(n).

02Key insight

Each answer is prefix-product times suffix-product. Write prefixes into the output, then sweep right-to-left with a running suffix to get O(1) extra space.

03Solution

solution.pypython12 lines

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

Try it first.

TimeO(n)

SpaceO(1) extra (output excluded)

tests.py · 3 passing

tests.pypython3 lines

assert product_except_self([1,2,3,4]) == [24,12,8,6]
assert product_except_self([-1,1,0,-3,3]) == [0,0,9,0,0]
assert product_except_self([0,0]) == [0,0]

04Staff-level follow-up

How would you parallelise it across machines? It's a prefix scan: each partition computes its local product, an exclusive scan over partition totals gives offsets, then each partition finishes locally.