Legend top row nums · dashed row res · blue outline = the elements the running product covers
public int[] productExceptSelf(int[] nums) { int n = nums.length; int[] res = new int[n]; Arrays.fill(res, 1); int prefix = 1; for (int i = 0; i < n; i++) { res[i] = prefix; // product of nums[0..i-1] prefix *= nums[i]; } int suffix = 1; for (int i = n - 1; i >= 0; i--) { res[i] *= suffix; // times product of nums[i+1..n-1] suffix *= nums[i]; } return res;}
- i
- —
- nums[i]
- —
- prefix
- 1
- suffix
- —
- res
- —
Why it works
- Brute force multiplies the other n − 1 values for every index: O(n²). Dividing the total product by
nums[i]is O(n), but the problem forbids division and it breaks on zeros. - Split the answer at
i:res[i]= (product of everything left ofi) × (product of everything right ofi). One left-to-right pass leaves the left half in each slot; one right-to-left pass multiplies in the right half. - Why O(n) and O(1): two passes over the array, and each running product is a single number. The output array does not count as extra space.
- Pitfall: write
res[i]before multiplying the running product bynums[i]. Swap the two lines and every slot includes its own value. - Zeros need no special case. One zero makes every slot except its own 0; two zeros make every slot 0. The passes produce both without branching.