#238 Product of Array Except Self
frequently reported atPayPalUberAppleAmazonMicrosoftBloomberg
the problem
In plain words
Return an array where answer[i] is the product of every element except nums[i]. Run in O(n) and do not use division.
in nums = [1,2,3,4]
out [24,12,8,6]
in nums = [-1,1,0,-3,3]
out [0,0,9,0,0]
- 2 ≤ n ≤ 10⁵
- -30 ≤ nums[i] ≤ 30
- Every prefix/suffix product fits in a 32-bit int
- Follow-up: O(1) extra space (the output array doesn't count)
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternPrefix & suffix passes
Everything except i = (everything left of i) × (everything right of i). Both sides are running products you can build in one pass each.
solutions
From brute force to optimal
For each index, multiply every other element.
- For each i: product = 1; multiply nums[j] for all j ≠ i.
n − 1 multiplications for each of n positions.
Only the output array.
class Solution { public int[] productExceptSelf(int[] nums) { int n = nums.length; int[] answer = new int[n]; for (int i = 0; i < n; i++) { int product = 1; for (int j = 0; j < n; j++) if (j != i) product *= nums[j]; answer[i] = product; } return answer; }}left[i] = product before i, right[i] = product after i, answer = left × right.
- Fill left[] left to right.
- Fill right[] right to left.
- Multiply them pairwise.
Three linear passes.
Two helper arrays.
class Solution { public int[] productExceptSelf(int[] nums) { int n = nums.length; int[] left = new int[n], right = new int[n], answer = new int[n]; left[0] = 1; // nothing to the left of index 0 for (int i = 1; i < n; i++) left[i] = left[i - 1] * nums[i - 1]; right[n - 1] = 1; // nothing to the right of the end for (int i = n - 2; i >= 0; i--) right[i] = right[i + 1] * nums[i + 1]; for (int i = 0; i < n; i++) answer[i] = left[i] * right[i]; return answer; }}Store left products directly in answer, then sweep from the right with a single running product.
- answer[i] = product of nums[0..i−1].
- right = 1; for i from n−1 down: answer[i] = right; right = nums[i].
Two linear passes.
One variable besides the required output.
class Solution { public int[] productExceptSelf(int[] nums) { int n = nums.length; int[] answer = new int[n]; answer[0] = 1; for (int i = 1; i < n; i++) { answer[i] = answer[i - 1] * nums[i - 1]; // product of everything LEFT of i } int right = 1; // product of everything RIGHT of i for (int i = n - 1; i >= 0; i--) { answer[i] *= right; // left part x right part right *= nums[i]; } return answer; }}Dry run
in the room
How to say it in the interview
talk track
- Mention division first and why it's banned/fragile: one zero breaks it, two zeros make everything 0.
- Draw [a, b, c, d] and write answer[2] = (a·b) × (d) — the prefix/suffix split becomes obvious.
- Finish with the O(1) version and state that the output array doesn't count as extra space.
traps
- Using division — fails on zeros and is forbidden.
- Off-by-one: the prefix for i is the product before i, so answer[0] = 1.
what they ask next
Follow-ups
What if division were allowed?
Count zeros. Two or more → all 0. Exactly one → only that index gets the product of the rest. None → total / nums[i].
before you submit
Edge cases to test
- One zero → only that index gets a non-zero product.
- Two or more zeros → every answer is 0.
- n = 2 → the two numbers simply swap places.
- Negatives keep their signs: [-2,-3,4,1] → [-12,-8,6,24].
practise next
Similar problems
- #42Trapping Rain WaterHardin Two Pointers
- #303Range Sum Query - ImmutableEasyin Hashing