Product of Array Except Self

Hard · rating 1450 · Arrays, Prefix Sum

The first line contains n. The second line contains n integers. Print an array (space-separated) where each position holds the product of all other elements except the one at that position. Do not use division.

Constraints: 2 ≤ n ≤ 105

Editorial

Approach

Division is disallowed (and breaks on zeros), so build the answer from two sweeps. First pass left-to-right: each position holds the product of everything to its left. Second pass right-to-left: multiply in the product of everything to its right.

n = len(nums); res = [1]*n
left = 1
for i in range(n):
    res[i] = left; left *= nums[i]
right = 1
for i in range(n-1, -1, -1):
    res[i] *= right; right *= nums[i]
return res

Complexity

Time: O(n). Space: O(1) extra, besides the output.

Related problems

Open Product of Array Except Self in Code Arena →