Product of Array Except Self
Problem
nums, build answer where
answer[i] is the product of every element except nums[i].
You may not use division, and the solution must run in O(n) time.[1,2,3,4]Output[24,12,8,6][-1,1,0,-3,3]Output[0,0,9,0,0]2 ≤ n ≤ 105 · -30 ≤ nums[i] ≤ 30 · every product fits in a 32-bit int · Follow-up: O(1) extra space (output excluded).
Try it yourself
class Solution {
public int[] productExceptSelf(int[] nums) {
}
}
answer[i] = (product of everything left of i) × (product of
everything right of i). Both sides are running products you can sweep in one pass each.Instinct "In place", "O(1) extra space" or "one pass" over an array? Think write pointer, reversal, prefix/suffix passes or using indices as storage.
Memory hack Read fast, write slow, reverse to rotate, and let the index be the hash.
Open the Array Manipulation guide →Approaches
Brute ForceNested Loops
O(n2)Space O(1)For every index i, multiply all nums[j] with
j ≠ i. Directly follows the definition, with no division needed.
public int[] productExceptSelf(int[] nums) { int n = nums.length; int[] output = new int[n]; for (int i = 0; i < n; i++) { output[i] = 1; for (int j = 0; j < n; j++) { if (i != j) output[i] *= nums[j]; } } return output; }
Correct but quadratic — 1010 operations at n = 105.
BetterPrefix & Suffix Arrays
O(n)Space O(n)Precompute prefix[i] = product of nums[0..i-1] and
suffix[i] = product of nums[i+1..n-1] (both start at 1).
Then output[i] = prefix[i] * suffix[i]. Zeros are handled naturally.
public int[] productExceptSelf(int[] nums) { int n = nums.length; int[] prefix = new int[n], suffix = new int[n], output = new int[n]; prefix[0] = 1; for (int i = 1; i < n; i++) prefix[i] = prefix[i - 1] * nums[i - 1]; suffix[n - 1] = 1; for (int i = n - 2; i >= 0; i--) suffix[i] = suffix[i + 1] * nums[i + 1]; for (int i = 0; i < n; i++) output[i] = prefix[i] * suffix[i]; return output; }
Linear time, but two extra arrays of size n.
OptimalOutput as Prefix + Running Suffix
O(n)Space O(1) extraStore the prefix products directly in output. Then sweep right-to-left
with a single variable right (product of everything to the right) and
multiply it in. The output array doesn't count as extra space.
public int[] productExceptSelf(int[] nums) { int n = nums.length; int[] output = new int[n]; output[0] = 1; for (int i = 1; i < n; i++) output[i] = output[i - 1] * nums[i - 1]; int right = 1; // product of nums[i+1..n-1] for (int i = n - 1; i >= 0; i--) { output[i] *= right; right *= nums[i]; } return output; }
Dry run[1,2,3,4]
- pass 11126left products
- i=31126i6×1=6, right=4
- i=2118i62×4=8, right=12
- i=1112i861×12=12, right=24
- i=024i12861×24=24 ✔
Two passes, constant extra memory — answers the follow-up.
0 breaks it (and division is
banned anyway) — prefix/suffix needs no zero special-casing.At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Nested Loops | O(n2) | O(1) |
| Better | Prefix & Suffix Arrays | O(n) | O(n) |
| Optimal | Output as Prefix + Running Suffix | O(n) | O(1) extra |
- Using division — forbidden, and fails when the array contains zeros.
- Off-by-one:
prefix[i]must excludenums[i]. - Updating
rightbefore multiplying it in — includesnums[i]itself.
- Draw the left and right product rows on the whiteboard; the formula becomes obvious.
- Clarify that the output array is not counted as extra space.
- Walk through a zero (and two zeros) to show no special handling is needed.