Product of Array Except Self
Compute every element's product-of-the-rest without division, using prefix and suffix passes
Problem Statement
Given an integer array nums, return an array answer where answer[i] is the product of all elements except nums[i].
You must solve it in O(n) time and without using the division operator.
Input: nums = [1, 2, 3, 4]
Output: [24, 12, 8, 6]
Why: 24 = 2×3×4, 12 = 1×3×4, 8 = 1×2×4, 6 = 1×2×3
Input: nums = [-1, 1, 0, -3, 3]
Output: [0, 0, 9, 0, 0]Intuition
The tempting shortcut is: compute the total product once, then divide it by each element. It is O(n) — and it is banned, for a good reason.
Why division fails even if it were allowed
A single zero makes the total product 0, and 0 / 0 is undefined. Two zeros make every answer 0. Handling this needs special cases for "no zeros", "one zero", and "two or more zeros" — fragile code that the constraint exists to steer you away from.
Here is the framing that works. Everything except nums[i] splits cleanly into two halves:
answer[i] = (product of everything to the LEFT of i)
× (product of everything to the RIGHT of i)For nums = [1, 2, 3, 4] at i = 2: left is 1 × 2 = 2, right is 4, so answer[2] = 8. ✓
The key insight
Both halves are running products, exactly like the running sums in Running Sum of 1d Array — just with × instead of +.
One left-to-right pass computes every prefix product. One right-to-left pass computes every suffix product. Multiply them together and you are done. No division, two passes, O(n).
By convention the product of an empty range is 1 (the multiplicative identity), so answer[0]'s left product is 1 and the last element's right product is 1.
Approach
The clever part is doing this with no extra arrays beyond the output.
Pass 1 — fill the output with prefix products
Walk left to right carrying left = 1. Write answer[i] = left, then multiply left *= nums[i].
Writing before multiplying is what excludes nums[i] itself.
Pass 2 — multiply in the suffix products
Walk right to left carrying right = 1. Do answer[i] *= right, then right *= nums[i].
Each cell already held its left product; now it also carries its right product.
Return answer
Only one array was allocated, and the problem states the output array does not count toward extra space.
Watch it run
Solution
def product_except_self(nums: list[int]) -> list[int]:
"""answer[i] = product of every element except nums[i], no division."""
n = len(nums)
answer = [1] * n
# Pass 1: answer[i] = product of everything to the left of i.
left = 1
for i in range(n):
answer[i] = left # write before multiplying — excludes nums[i]
left *= nums[i]
# Pass 2: fold in the product of everything to the right of i.
right = 1
for i in range(n - 1, -1, -1):
answer[i] *= right
right *= nums[i]
return answerWhy zeros need no special handling
With nums = [1, 0, 3]: the prefix pass gives [1, 1, 0] and the suffix pass multiplies by [0, 3, 1], yielding [0, 3, 0]. The zero simply propagates into every product that legitimately contains it, and is absent from answer[1] — the one position that excludes it. This falls out of the arithmetic with no branches at all.
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(1)
- Time — two linear passes,
2noperations. - Space —
O(1)extra. The output array does not count, and only two scalar accumulators are used. The more obvious version, which builds separateprefixandsuffixarrays, is equally fast but usesO(n)extra space — this one earns the constant-space claim by reusing the output.
Edge Cases
Related Problems
- Running Sum of 1d Array — the same prefix idea with addition
- Find Pivot Index — another "everything except me, split into two sides" problem
- Trapping Rain Water — prefix maximum from the left, suffix maximum from the right