Product of Array Except Self
Problem Statement
Given an integer array nums, return an array answer where answer[i] is the product of every value in nums except nums[i]. You must solve it without using division and in linear time.
Input
An integer array nums.
Output
An integer array answer where each position stores the product of all numbers except the number at that position.
Constraints
- •
2 <= nums.length <= 10^5 - •
-30 <= nums[i] <= 30 - •
The product of any prefix or suffix of nums fits in a 32-bit signed integer - •
You must write an algorithm that runs in O(n) time and does not use division
Examples
Example 1
nums = [1,2,3,4]
[24,12,8,6]Example 2
nums = [-1,1,0,-3,3]
[0,0,9,0,0]Example 3
nums = [0,0]
[0,0]Learning Objectives
- Recognise when division is tempting but invalid because of zeros and the no-division requirement.
- Separate each answer into the product of values strictly to its left and strictly to its right.
- Use the output array as prefix-product storage without counting it as extra space.
- Explain why two directional passes cover every excluded-self product exactly once.
Intuition
Pattern Recognition
Each answer needs everything except the current value. The direct O(n^2) idea recomputes almost the same product for every index, and division is not allowed because zeros create separate cases. The reusable pattern is to split the product around the index: left side times right side.
The in-place insight is that the output array can first store left products. A second reverse pass carries one running right product and multiplies it into the stored left product. That gives the final answer while using only constant extra variables beyond the required output.
Common mistakes
- ×Using division and then trying to patch zero cases even though the problem explicitly forbids division.
- ×Including **nums[i]** in either the prefix or suffix product for index **i**.
- ×Allocating separate prefix and suffix arrays when the answer array can store the prefix side.
- ×Updating the suffix product before multiplying it into **answer[i]**, which accidentally includes the current value.
Algorithm Explanation
Key idea
For each index, answer[i] = product of values before i * product of values after i. Store the left product in answer[i] during a forward pass. Then walk backward with a running suffix product and multiply it into each cell before the suffix absorbs the current value.
Walkthrough
For nums = [1,2,3,4], the forward pass writes prefix products before each index: answer = [1,1,2,6]. These mean there is no value before index 0, product 1 before index 1, product 1 * 2 before index 2, and product 1 * 2 * 3 before index 3.
Now the suffix pass starts from the right with suffix 1. At index 3, multiply by 1 and then suffix becomes 4. At index 2, multiply the stored 2 by suffix 4 to get 8, then suffix becomes 12. At index 1, 1 * 12 becomes 12. At index 0, 1 * 24 becomes 24. The final array is [24,12,8,6].
Algorithm
- Allocate answer with the same length as nums.
- Set prefix = 1.
- Scan left to right. Store prefix in answer[i], then multiply prefix by nums[i].
- Set suffix = 1.
- Scan right to left. Multiply answer[i] by suffix, then multiply suffix by nums[i].
- Return answer.
Solutions
Solution: Prefix in output plus reverse suffix pass
The output array stores the product of values to the left of each index. A single reverse pass carries the product of values to the right and multiplies it into the existing output cell.
Step-by-step
- Create answer and set a running prefix to 1.
- For each index from left to right, write the current prefix before multiplying by the current value.
- Set a running suffix to 1.
- For each index from right to left, multiply answer[index] by suffix before multiplying suffix by nums[index].
- Return answer, which now contains left product times right product for every index.
O(n)
O(1)
The output array is required by the problem and is not counted as extra space; only two scalar products are stored.
Java implementation
Dry Run
Sample input
nums = [1,2,3,4]. Track the prefix pass that fills answer, then the suffix pass that completes each value.
| pass | index | nums[index] | running product before | answer[index] after step | running product after |
|---|---|---|---|---|---|
| prefix | 0 | 1 | 1 | 1 | 1 |
| prefix | 1 | 2 | 1 | 1 | 2 |
| prefix | 2 | 3 | 2 | 2 | 6 |
| prefix | 3 | 4 | 6 | 6 | 24 |
| suffix | 3 | 4 | 1 | 6 | 4 |
| suffix | 2 | 3 | 4 | 8 | 12 |
| suffix | 1 | 2 | 12 | 12 | 24 |
| suffix | 0 | 1 | 24 | 24 | 24 |
The answer starts as left products [1,1,2,6] and finishes as [24,12,8,6] after multiplying by right products.
Interview Tips
Lead with the split: every index needs the product on the left times the product on the right. Then state why division is not acceptable: zeros make quotient logic branchy and the prompt forbids it. Emphasize that the answer array is not counted as extra space, so using it for prefix products is the intended constant-space optimization.
Likely follow-ups
- How would you handle products that exceed 32-bit integers?
- How would the answer change if division were allowed and zeros were present?
- Can you return the same result if the input arrives as a stream that can be read only once?
- How would you adapt the idea for products modulo a prime?
Similar Problems
Key Takeaways
- Products except self decompose into left product times right product.
- The output array can store intermediate prefix products without extra counted space.
- Multiply by the suffix before updating the suffix with the current value.
- Avoid division because zeros create invalid quotient assumptions.