Appearance
4.4.7 — Product of Array Except Self
LeetCode 238 · Medium · ★ Blind 75
The problem
Return an array where position i holds the product of every element except nums[i].
nums = [1, 2, 3, 4]
answer = [24, 12, 8, 6]
nums = [-1, 1, 0, -3, 3]
answer = [ 0, 0, 9, 0, 0]Up to 100,000 elements. No division, and O(n) time. The follow-up asks for O(1) extra space, not counting the output array.
In plain English, for every number in the list, you need to multiply all the other numbers together and put that result in the same spot. If the list is [1, 2, 3, 4], the first spot should be 2 * 3 * 4 = 24, the second spot should be 1 * 3 * 4 = 12, and so on.
Why division is banned
Without the rule this is two lines: multiply everything, divide by each element. A single zero breaks it, and handling zeros properly needs three branches — no zeros, exactly one zero, two or more zeros.
The solution below has no special case at all. Zeros and negatives flow through the same arithmetic. That is the real reason the rule is there: it is pointing you at the better design, not setting a puzzle.
The pattern
For each position, the answer is everything to its left times everything to its right.
\text{answer}[i] = \left(\prod_{j < i} \text{nums}[j]\right) \times \left(\prod_{j > i} \text{nums}[j]\right)
The brute force recomputes both halves at every index. But the left product for position i+1 is just the left product for position i times one more number. Carrying it in a variable costs nothing. Think of it like a train picking up passengers. If you want to know who is on the train at station 4, you don't need to send someone back to station 1 to recount everyone who boarded. You just take the passenger count from station 3 and add whoever boarded at station 3. We do exactly this, but with multiplication instead of addition.
So: two sweeps in opposite directions, each carrying a running product.
The leftmost prefix value is 1, not nums[0]. Nothing sits to the left of position 0, and the product of no numbers is 1. That leading 1 is what makes the boundary work without an if.
The solution
python
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
n = len(nums)
answer = [1] * n
prefix = 1
for i in range(n):
answer[i] = prefix # write BEFORE folding nums[i] in
prefix *= nums[i]
suffix = 1
for i in range(n - 1, -1, -1):
answer[i] *= suffix # same discipline, mirrored
suffix *= nums[i]
return answerts
function productExceptSelf(nums: number[]): number[] {
const n = nums.length;
const answer = new Array(n).fill(1);
let prefix = 1;
for (let i = 0; i < n; i++) {
answer[i] = prefix;
prefix *= nums[i];
}
let suffix = 1;
for (let i = n - 1; i >= 0; i--) {
answer[i] *= suffix;
suffix *= nums[i];
}
return answer;
}The order of the two lines inside each loop is the whole trick. When answer[i] = prefix runs, prefix holds the product of everything before i, because nums[i] has not been folded in yet. Swap the lines and every slot includes itself, which is a different and wrong array.
Say the invariant out loud while writing it: prefix is the product of everything strictly before i, and suffix is the product of everything strictly after i. Both loops are then just "use it, then update it".
Code Walkthrough
answer = [1] * n: We create our output array filled with 1s. This is crucial because we will be multiplying into these slots, and 1 is the multiplicative identity.for i in range(n):: We sweep left-to-right.answer[i] = prefix: We drop the product of everything beforeiinto the current slot.prefix *= nums[i]: We updateprefixto includenums[i]so it's ready for the next iteration (i+1).for i in range(n - 1, -1, -1):: We sweep right-to-left.answer[i] *= suffix: We multiply the existing value (which is the prefix product) by thesuffix(which is the product of everything afteri). This perfectly aligns with our formula!suffix *= nums[i]: We updatesuffixfor the next iteration (i-1).
Trace
nums = [1, 2, 3, 4].
Forward: answer becomes [1, 1, 2, 6] while prefix runs 1 → 1 → 2 → 6 → 24.
Backward, starting with suffix = 1:
i | suffix in | answer[i] becomes | suffix after |
|---|---|---|---|
| 3 | 1 | 6 × 1 = 6 | 4 |
| 2 | 4 | 2 × 4 = 8 | 12 |
| 1 | 12 | 1 × 12 = 12 | 24 |
| 0 | 24 | 1 × 24 = 24 | 24 |
[24, 12, 8, 6].
Why zeros need no branch
Take [1, 0, 3]. The prefix pass gives [1, 1, 0]. The suffix pass multiplies in [0, 3, 1]. Result [0, 3, 0].
Check by hand: excluding index 0 gives 0·3 = 0 ✓, excluding index 1 gives 1·3 = 3 ✓, excluding index 2 gives 1·0 = 0 ✓.
The zero lands in exactly the positions that should see it, and never in the position it came from, because no sweep ever multiplies nums[i] into answer[i]. Two zeros give all zeros for the same reason. Negatives take care of themselves.
Complexity
O(n) time. O(1) extra space, since the output array is excluded by the problem and the only other memory is two scalars.
Time Complexity: We do one pass left-to-right taking O(n) steps. Then we do a second pass right-to-left taking another O(n) steps. Each step is just one multiplication and one assignment, which takes O(1) time. Overall time is O(2n), which simplifies to O(n). Space Complexity: We allocate an answer array of size n, but the problem explicitly states this doesn't count towards extra space. The only other memory we use are the prefix and suffix variables, which take O(1) space. Thus, the extra space complexity is O(1).
A version that builds separate prefix[] and suffix[] arrays first is easier to read and is O(n) extra space. That is a fine first answer — then fold them into the output array to meet the follow-up. Showing the improvement is better than starting tight.
Edge cases
Two elements is the minimum input and works. The constraints promise every prefix and suffix product fits in a 32-bit integer, which is worded that way because it is the intermediate running values that could overflow, not the answer. Python and JavaScript cannot hit it here; Java and C++ can.
Where this goes next
- Prefix sums — the same shape with
+. 4.2. - Trapping Rain Water — the water above each position is capped by the tallest bar to its left and to its right. That is this structure with
maxinstead of×. 4.5. - Candy — one pass enforces the left rule, one enforces the right, and the answer is the larger of the two.
The rule: when the answer at each position depends on a prefix and a suffix, do two passes in opposite directions and pick the operator to match the question.
What the interviewer will push on
"Why forbid division?" Zeros force three branches; this version needs none.
"O(1) extra space?" Reuse the output array for the prefix pass and keep the suffix in a scalar.
"What if the values were floats?" Division stops being safe even without zeros, because floating-point multiply and divide are not exact inverses. This solution does not care.
"What if the array keeps changing and you must answer many queries?" Precomputed passes are invalidated by every update, so the right structure becomes a segment tree over products — O(\log n) per update and query. Chapter 4.13.4.
One thing to volunteer: state the invariant before writing the loops. That is how you prove the code is right rather than hoping the tests agree.
Next: 4.4.8 Valid Sudoku — back to sets, with the interesting part being how to name a region of a grid with one number.