roadmap/arrays-hashing/Product of Array Except Self

Product of Array Except Self

MediumAmazonGoogleMetaMicrosoft

Problem

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

Intuition — the key insight

For each index i: answer = (product of all elements left of i) × (product of all elements right of i). Compute prefix products left-to-right, then multiply by suffix products right-to-left in a second pass.

Approach

Prefix × suffix pass

Pass 1: result[i] = product of nums[0..i-1]. Pass 2: running suffix product from right, multiply into result[i].

Complexity

Time

O(n)

Space

O(1) extra

Two passes, output array doesn't count as extra space.

Solution code

Python

def productExceptSelf(self, nums: List[int]) -> List[int]:
    n = len(nums)
    result = [1] * n
    
    # Left pass: result[i] = product of nums[0..i-1]
    prefix = 1
    for i in range(n):
        result[i] = prefix
        prefix *= nums[i]
    
    # Right pass: multiply by product of nums[i+1..n-1]
    suffix = 1
    for i in range(n-1, -1, -1):
        result[i] *= suffix
        suffix *= nums[i]
    
    return result

Edge cases to remember

⚠Array with zeros: prefix/suffix naturally handle zeros

⚠Single element: output is [1]

Hints

What pattern do you think this problem uses?