Product of Array Except Self: The Prefix-Suffix Trick
Solve Product of Array Except Self in O(n) time with no division — prefix and suffix products explained with a worked walkthrough, JavaScript code, and complexity.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Product of Array Except Self looks like a one-liner until you read the fine print: no division allowed, and it must run in linear time. Those two constraints together rule out the obvious answer and force you into a genuinely useful pattern — building an answer from a prefix pass and a suffix pass that meet in the middle.
The reframe here shows up everywhere: range-sum queries, trapping rain water, candy distribution. Once you see that every position's answer is "everything to my left times everything to my right," a whole class of array problems collapses into two clean loops.
The problem
Given an integer array nums, return an array ans where ans[i] equals the product of every element in nums except nums[i]. You must solve it without the division operator, and the expected runtime is O(n).
Input: nums = [1, 2, 3, 4]
Output: [24, 12, 8, 6]
// ans[0] = 2*3*4 = 24
// ans[1] = 1*3*4 = 12
// ans[2] = 1*2*4 = 8
// ans[3] = 1*2*3 = 6Two constraints do all the work of making this a real problem:
- No division. The cheap trick — multiply everything, then divide out
nums[i]— is banned. It also breaks on zeros anyway. - Linear time. You get one or two passes, not a nested loop.
The brute force baseline
The direct translation of the problem statement: for each index, walk the whole array and multiply in every other element.
function productExceptSelf(nums) {
const n = nums.length;
const ans = Array(n).fill(1);
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (i !== j) ans[i] *= nums[j];
}
}
return ans;
}This is correct and needs no division, but the inner loop re-multiplies the same spans over and over. Computing ans[0] scans elements 1..n-1; computing ans[1] re-scans almost the same range. That's O(n²) total — fine for a handful of elements, hopeless on the 10⁵-length arrays LeetCode throws at you.
The key insight: split the answer at index i
Look at any single answer. For nums = [1, 2, 3, 4], the value at index 2 is 1*2 * 4 — the product of everything left of index 2, multiplied by the product of everything right of it. That's true for every position:
ans[i] = (product of nums[0..i-1]) * (product of nums[i+1..n-1])
= prefix[i] * suffix[i]If you had a prefix array (running product from the left, excluding self) and a suffix array (running product from the right, excluding self), the answer would just be their element-wise product. No division, and each array is one linear pass.
The final refinement drops the extra arrays entirely. Fill ans with the prefix products on the first pass, then walk backward multiplying in a single rolling suffix variable. The output array doubles as scratch space, so the only extra memory is two integers.
The optimal solution
This is the exact two-pass algorithm the visualizer steps through:
var productExceptSelf = function (nums) {
const n = nums.length;
const ans = Array(n).fill(1);
// Left pass: prefix products
let prefix = 1;
for (let i = 0; i < n; i += 1) {
ans[i] = prefix; // product of everything left of i
prefix *= nums[i]; // fold nums[i] into the running prefix
}
// Right pass: suffix products
let suffix = 1;
for (let i = n - 1; i >= 0; i--) {
ans[i] *= suffix; // combine left product with right product
suffix *= nums[i]; // fold nums[i] into the running suffix
}
return ans;
};The ordering inside each loop is the whole trick. In the left pass you write ans[i] = prefix before folding nums[i] into prefix — that guarantees ans[i] holds the product of strictly-earlier elements and never includes itself. The right pass mirrors it exactly: multiply first, then update suffix. That "assign, then update" discipline is why the self-exclusion works with zero special-casing.
Walkthrough
Trace nums = [1, 2, 3, 4]. First the left pass builds prefix products into ans:
| i | prefix (before) | ans[i] = prefix | prefix *= nums[i] | ans so far |
|---|---|---|---|---|
| 0 | 1 | 1 | 1 * 1 = 1 | [1, 1, 1, 1] |
| 1 | 1 | 1 | 1 * 2 = 2 | [1, 1, 1, 1] |
| 2 | 2 | 2 | 2 * 3 = 6 | [1, 1, 2, 1] |
| 3 | 6 | 6 | 6 * 4 = 24 | [1, 1, 2, 6] |
After the left pass, ans = [1, 1, 2, 6] — each slot holds the product of everything to its left. Now the right pass walks backward, folding in the suffix:
| i | suffix (before) | ans[i] *= suffix | suffix *= nums[i] | ans so far |
|---|---|---|---|---|
| 3 | 1 | 6 * 1 = 6 | 1 * 4 = 4 | [1, 1, 2, 6] |
| 2 | 4 | 2 * 4 = 8 | 4 * 3 = 12 | [1, 1, 8, 6] |
| 1 | 12 | 1 * 12 = 12 | 12 * 2 = 24 | [1, 12, 8, 6] |
| 0 | 24 | 1 * 24 = 24 | 24 * 1 = 24 | [24, 12, 8, 6] |
At index 1, for example, ans[1] was 1 (nothing to its left) and gets multiplied by suffix = 12 (which is 3*4), landing on 12 — exactly 1*3*4. The final result is [24, 12, 8, 6].
Complexity
| Metric | Value | Why |
|---|---|---|
| Time | O(n) | Two independent single passes over the array — 2n work, no nesting |
| Space | O(1) extra | Only prefix and suffix scalars; the ans array is the required output, not counted |
| Brute force time | O(n²) | An inner scan of up to n elements for each of the n positions |
The output array is excluded from the space count by convention, which is what lets this claim O(1) extra space — the standard interview-grade answer.
Common mistakes
- Reaching for division. Multiply-everything-then-divide is banned by the problem, and it silently breaks whenever the array contains a zero (you'd divide by zero, or get the wrong answer for the zero's own slot).
- Updating
prefixbefore assigning. If you writeprefix *= nums[i]beforeans[i] = prefix, the answer includesnums[i]itself. Assign first, then update — in both passes. - Allocating separate prefix and suffix arrays. It works and is easier to reason about at first, but it's O(n) extra space. Reusing
ansand a rolling scalar is the version interviewers want. - Mishandling zeros manually. People add special branches counting zeros. You don't need any — the prefix/suffix math produces
0in every non-zero slot and the real product in the single zero slot automatically. Two zeros correctly zero out everything. - Getting the suffix loop bounds wrong. The right pass must start at
n - 1and run down to0inclusive; an off-by-one here silently corrupts the first or last answer.
Where this pattern shows up next
The "answer at each index = something-left combined with something-right" idea is the backbone of a lot of array work. These neighbors drill the same in-place, single-scan discipline:
- Remove Duplicates from Sorted Array — a write pointer building the answer in place during one pass.
- Remove Element — the same overwrite-in-place technique on a filter condition.
- Reverse String — two indices converging from both ends, the mirror of prefix-meets-suffix.
- Best Time to Buy and Sell Stock — a running "best so far" that plays the exact role
prefixdoes here.
You can also step through Product of Array Except Self interactively to watch the prefix row fill left-to-right and the suffix row multiply back in from the right.
FAQ
Why can't I just multiply everything and divide by nums[i]?
The problem explicitly bans the division operator, and for good reason: division breaks on zeros. If any element is 0, dividing the total product by that element is undefined, and if two elements are 0 the total product is itself 0, so you can't recover the individual answers. The prefix-suffix approach sidesteps division entirely and handles any number of zeros with no extra code.
How does this solve Product of Array Except Self without division in O(n)?
Every answer is the product of all elements to the left of an index times all elements to the right. A left-to-right pass writes those left products into the output array, and a right-to-left pass multiplies in the right products using a single rolling variable. Two linear passes with constant extra work per element give O(n) time, and multiplication alone means no division is ever needed.
What is the space complexity of the optimal solution?
O(1) extra space. Beyond the output array — which the problem requires you to return and is therefore not counted — the algorithm uses only two integer variables, prefix and suffix. The naive prefix-and-suffix-array version uses O(n) extra memory, so folding both into the output array and a scalar is the improvement interviewers look for.
How does the algorithm handle zeros in the array?
Automatically, with no special cases. If exactly one element is zero, every other position's product includes that zero and becomes 0, while the zero's own slot is the product of all the non-zero elements — the prefix/suffix multiplication produces both correctly. If two or more elements are zero, every position's product picks up at least one zero, so the entire output is zeros, which is also exactly what the passes compute.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.