Product of Array Except Self
LeetCode 238 • Medium • Arrays
Return array where ans[i] = product of all elements except nums[i]. No division. Pass 1: prefix products. Pass 2: suffix × result. O(1) extra space.
TimeO(n)two passes
SpaceO(1)output doesn't count
prefix: —
suffix: —
Ready
Press Play. Pass 1: result[i] = prefix (product of nums[0..i-1]). Pass 2: result[i] *= suffix (product of nums[i+1..n-1]).
TimeO(n)visit each index
SpaceO(n)call stack
Recursive: prefix(i) = product nums[0..i-1]; suffix(i) = product nums[i+1..n-1]; result[i] = prefix(i) × suffix(i). Iterative is preferred for O(1) space.
Practice until you don't need to look. Use the guide comments below as scaffolding. The green highlights are the nuances to burn into memory.
PATTERN ▸ Prefix pass + suffix pass O(n) · O(1)
① INIT
n = len(nums)
result = [1] * n
② PREFIX PASS (left to right)
prefix = 1
for i in range(n):
result[i] = prefix; prefix *= nums[i]
③ SUFFIX PASS (right to left)
suffix = 1
for i in range(n-1, -1, -1):
result[i] *= suffix; suffix *= nums[i]
④ RETURN
return result
▼ your implementation ▼
Verify your solution: