Product of Array Except Self
Compute prefix products and suffix products in two passes — O(n), no division.
arraysprefix-suffix
Intro
Return an array where output[i] is the product of all elements except nums[i], in O(n) without using division and O(1) extra space (output array doesn't count).
Key insight
output[i] = (product of everything to the left of i) × (product of everything to the right of i). Compute both in two sweeps.
Approach
- 1First pass: output[i] = product of nums[0..i-1] (running prefix).
- 2Second pass right-to-left: maintain a running suffix product; multiply it into output[i].
Complexity
Time
O(n)
Space
O(1) extra
Code
Snippetjava
int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] out = new int[n];
out[0] = 1;
for (int i = 1; i < n; i++) out[i] = out[i - 1] * nums[i - 1];
int suffix = 1;
for (int i = n - 1; i >= 0; i--) {
out[i] *= suffix;
suffix *= nums[i];
}
return out;
}Pitfalls
- Using division — fails on inputs with zeros and is generally an interview anti-pattern here.
- Treating `output[0]` carelessly — must be initialised to 1.
Variants & follow-ups
- Maximum Product Subarray (LC 152)