📚 Table of Contents
📋 Problem Statement
Given an integer array nums, build answer such that
answer[i] equals the product of all elements except nums[i].
Constraints require O(N) time and no division. The output array itself does not count as extra space.
Examples
Input: [1,2,3,4]Output: [24,12,8,6]
Input: [-1,1,0,-3,3]Output: [0,0,9,0,0]
🎯 Real-World Analogy
Factory Line Multipliers
Each station has a multiplier. For station i, you need the multiplication of
every other station's factor, but not its own.
So you precompute what comes from the left side and what comes from the right side, then combine both at each station.
💡 Key Insights
answer[i] = prefix_before_i * suffix_after_i.- First pass writes left-prefix product into output.
- Second reverse pass multiplies by running right-suffix product.
- No division means this still works cleanly with zeros.
💻 Solution Approaches
Approach 1: Division with Zero Counting (Not Preferred)
Time: O(N) | Space: O(1)
Compute total product then divide by nums[i], with special zero handling.
Faster to explain, but violates problem requirement (no division).
Approach 2: Prefix and Suffix Arrays
Time: O(N) | Space: O(N)
Build two helper arrays for left and right products, then multiply pairwise.
Approach 3: Output Array + Running Suffix (Recommended)
Time: O(N) | Space: O(1) extra (excluding output)
Python Implementation
from typing import List
def product_except_self(nums: List[int]) -> List[int]:
n = len(nums)
answer = [1] * n
prefix = 1
for i in range(n):
answer[i] = prefix
prefix *= nums[i]
suffix = 1
for i in range(n - 1, -1, -1):
answer[i] *= suffix
suffix *= nums[i]
return answer
JavaScript Implementation
function productExceptSelf(nums) {
const n = nums.length;
const answer = new Array(n).fill(1);
let prefix = 1;
for (let i = 0; i < n; i += 1) {
answer[i] = prefix;
prefix *= nums[i];
}
let suffix = 1;
for (let i = n - 1; i >= 0; i -= 1) {
answer[i] *= suffix;
suffix *= nums[i];
}
return answer;
}
🔍 Step-by-Step Walkthrough
Trace [1,2,3,4]:
⚡ Complexity Analysis
Time: O(N) because we run one forward pass and one backward pass.
Space: O(1) extra because only two scalar accumulators
(prefix, suffix) are used beyond the required output array.
🔧 Edge Cases
- Single zero in input: only one index gets non-zero product.
- Multiple zeros: all outputs are zero.
- Negative numbers affect sign combinations.
- Minimum length
n=2still valid.
🧪 Test Cases
Python
def test_product_except_self():
assert product_except_self([1, 2, 3, 4]) == [24, 12, 8, 6]
assert product_except_self([-1, 1, 0, -3, 3]) == [0, 0, 9, 0, 0]
assert product_except_self([0, 4, 0]) == [0, 0, 0]
assert product_except_self([2, 3]) == [3, 2]
print("all tests passed")JavaScript
function testProductExceptSelf() {
console.assert(
JSON.stringify(productExceptSelf([1, 2, 3, 4])) === JSON.stringify([24, 12, 8, 6]),
"test 1"
);
console.assert(
JSON.stringify(productExceptSelf([-1, 1, 0, -3, 3])) === JSON.stringify([0, 0, 9, 0, 0]),
"test 2"
);
console.assert(
JSON.stringify(productExceptSelf([0, 4, 0])) === JSON.stringify([0, 0, 0]),
"test 3"
);
console.log("all tests passed");
}💼 Interview Tips
- Call out the "no division" constraint first.
- Explain why prefix and suffix decomposition is complete.
- Mention output-array-space convention explicitly.
- Demonstrate behavior with zero-heavy arrays.
🎓 Key Takeaways
- Prefix/suffix decomposition removes division cleanly.
- Two linear passes are enough for full result construction.
- Always test single-zero and multi-zero scenarios separately.