Arrays & Hashing · LC #238
Product of Array Except Self
Compute for each index the product of all other elements without using division. Teaches the two-pass prefix/suffix product pattern that achieves O(n) time with O(1) extra space.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
Given an integer array `nums`, return an array `answer` such that `answer[i]` is equal to the product of all elements except `nums[i]`. **Division is not allowed.**
Sample I/O
Input: nums = [1,2,3,4] Output: [24,12,8,6] Input: nums = [-1,1,0,-3,3] Output: [0,0,9,0,0]
Intuition
How to Think About It
Intuition
The product of everything except nums[i] equals (product of everything to the LEFT of i) × (product of everything to the RIGHT of i). Computing these two partial products in two passes and multiplying them gives the answer without ever dividing.
Core Concept
Left pass: result[i] = product of nums[0..i-1]. Start with result[0]=1 (no elements to the left). Right pass: maintain a running right product, scan right to left, multiply result[i] by it, then update right *= nums[i]. Output array doubles as left-product storage, so total extra space is O(1) (excluding the output array).
When to use
Any "product of all others" problem with a no-division constraint. Computing running products for financial returns. Generating prefix/suffix arrays for range queries. Template for "contribution of all except one element" patterns.
When NOT to use
When division IS allowed - simply compute total product then divide by nums[i] (handle zeros separately). When the array can have more than two zeros - the no-division two-pass still handles it correctly, but worth confirming edge cases.
Key Insights
What to Know Cold
- The two-pass trick reuses the output array for the left products, then overwrites it in-place during the right pass - no extra O(n) array needed.
- Zeros require no special handling in the prefix/suffix approach unlike the division method.
- With division allowed: total = product of non-zero elements; result[i] = total / nums[i] if nums[i] != 0, else count zeros to determine 0 or non-zero output.
- This is a specific instance of the prefix-sum pattern generalised to multiplication.
- Interviewers often follow up with: "what if there are zeros?" - confirm your approach handles nums=[-1,1,0,-3,3] correctly.
1 example
Worked Examples
Two-Pass Prefix × Suffix
nums = [1,2,3,4]. Compute product-except-self without division.
Left pass: result = [1,1,2,6]. Right pass (right=1): i=3→result[3]=6×1=6, right=4; i=2→result[2]=2×4=8, right=12; i=1→result[1]=1×12=12, right=24; i=0→result[0]=1×24=24.
nums = [1, 2, 3, 4]
n = len(nums)
result = [1] * n
for i in range(1, n):
result[i] = result[i-1] * nums[i-1] # left products
right = 1
for i in range(n-1, -1, -1):
result[i] *= right
right *= nums[i]
print(result) # [24, 12, 8, 6]One of the most-asked Amazon coding problems. Demonstrates prefix/suffix product thinking - the same pattern appears in Trapping Rain Water, Maximum Product Subarray, and range-product queries.