Skip to content
GKgkml.dev
← Problem set
#238MediumArrays & hashing

Product of Array Except Self

The tell: Every position needs an aggregate of everything else, and division is forbidden.

How you get there

  1. 1The answer at i is (product of everything left of i) × (product of everything right of i).
  2. 2One forward pass fills the left products directly into the output array.
  3. 3One backward pass multiplies in the right products using a single running variable.

Solution

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

    prefix = 1
    for i in range(len(nums)):
        out[i] = prefix
        prefix *= nums[i]

    suffix = 1
    for i in range(len(nums) - 1, -1, -1):
        out[i] *= suffix
        suffix *= nums[i]

    return out
Time
O(n)
Space
O(1) excluding the output

What goes wrong

Reaching for division breaks on a single zero, and breaks worse on two.

Test yourself on DSANext: Valid Anagram →