Product of Array Except Self
Medium Prefix & suffix products
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Return an array where each position holds the product of all other elements, without using division, in O(n).
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: for each index, the product of all the other numbers, without division.
Why this works: product of everything else = (product of everything on the left) × (product of everything on the right). Two passes build both.
Example: [1, 2, 3, 4]
left products: [1, 1, 2, 6]right products: [24, 12, 4, 1]multiply: [24, 12, 8, 6]
✦Hints open one at a time
↗Approach
Pass 1 (left to right): ans[i] = product of nums[0..i-1]. Pass 2 (right to left): keep a running product of nums[i+1..] and multiply it into ans[i]. Only the output array is used.
</>Solution (Java)
class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] ans = new int[n];
ans[0] = 1;
for (int i = 1; i < n; i++) ans[i] = ans[i - 1] * nums[i - 1]; // left products
int right = 1;
for (int i = n - 1; i >= 0; i--) {
ans[i] *= right; // times product of everything to the right
right *= nums[i];
}
return ans;
}
}!Common mistake
Dividing the total product by nums[i] — it's not allowed and fails when the array has a zero.
- Time: O(n).
- Space: O(1) extra besides the output.
