Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].
You must write an algorithm that runs in O(n) time and without using the division operation.
Example 1:
Input:nums = [1,2,3,4]
Output:[24,12,8,6]
Example 2:
Input:nums = [-1,1,0,-3,3]
Output:[0,0,9,0,0]
Constraints:
2 ≤ nums.length ≤ 10⁵
-30 ≤ nums[i] ≤ 30
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
Follow up: Can you solve it in O(1) extra space complexity? (The output array does not count as extra space.)
Hints
Hint 1Division is banned — think about what answer[i] really means.▼
answer[i] = product of everything to the left of i × product of everything to the right of i. If you had both of those values precomputed, each position is just one multiplication.
Hint 2Build prefix products in a forward pass.▼
Iterate left-to-right, maintaining a running product. For position i, set res[i] = prefix (product of all elements before i), then update prefix *= nums[i]. After this pass, res[i] holds the left product.
Hint 3Multiply in postfix products with a backward pass — no extra array needed.▼
Iterate right-to-left with a running postfix product. Multiply res[i] *= postfix (which already holds the left product), then update postfix *= nums[i]. You now have left × right for every position in O(n) time, O(1) extra space.
Brute Force Approach
O(n²) Time
🔄
For Each Element, Multiply All Others
Time O(n²)Space O(1)
For each position, compute its answer by multiplying every other element. Simple, correct, but O(n²).
1Outer loop over each index i.
2Inner loop: multiply all nums[j] where j ≠ i.
3For n = 10⁵, this performs 10¹⁰ multiplications — completely infeasible.
defproductExceptSelf(nums):
n = len(nums)
res = [1] * n
for i inrange(n):
for j inrange(n):
if i != j:
res[i] *= nums[j]
return res
Optimal Approach — Prefix & Postfix Arrays
O(n) Time
🏃
Two-Pass Prefix / Postfix Multiplication
Time O(n)Space O(1)
If we cannot use division, we can calculate the result by finding the product of all elements to the left of i (the prefix) and multiplying it by the product of all elements to the right of i (the postfix).
1Initialize an output array res with 1s. This counts as O(1) auxiliary space since it's the expected return value.
2Prefix Pass: Iterate left-to-right. For each i, set res[i] to the running prefix product, then multiply prefix by nums[i].
3Postfix Pass: Iterate right-to-left. Multiply res[i] by the running postfix product, then multiply postfix by nums[i].
READYPress ▶ or step forward to begin.
✓
—
Executing Code
defproductExceptSelf(nums):
res = [1] * len(nums)
prefix = 1
for i inrange(len(nums)):
res[i] = prefix
prefix *= nums[i]
postfix = 1
for i inrange(len(nums) - 1, -1, -1):
res[i] *= postfix
postfix *= nums[i]
return res
Time Complexity Analysis
Prefix passO(n)One left-to-right scan. At each index we do one read, one write, and one multiply — all O(1). Total: n operations.
Postfix passO(n)One right-to-left scan with identical constant-time operations. Together with the prefix pass, every element is visited exactly twice total.
TotalO(n) time · O(1) spaceTwo O(n) passes, no extra arrays beyond the output. The output array res is not counted as auxiliary space since it is the required return value.
Why ban division? Division would fail silently when the array contains zero — dividing the total product by 0 is undefined. The prefix/postfix approach handles zeros naturally: a zero propagates through multiplication exactly as intended, zeroing out all positions except its own without any special-case code.
Discussion
…