ASAPUtils
The signal
Two things stand out. First, “except self” — the answer at each index is built from two disjoint regions, left and right, that never overlap. Second, “without division” removes the cheap trick and forces you to see the structure.
Whenever an answer decomposes into “everything before me” and “everything after me”, think prefix and suffix sweeps. That idea reappears all the way through week 2’s prefix sums.
Approach ladder
1. Brute force — O(n²)
For each i, loop over everything else and multiply. Correct, too slow at n ≤ 10⁵.
2. Division — O(n), but wrong
Compute the total product, then divide by nums[i]. Forbidden by the problem, and genuinely
fragile: one zero and every non-zero position is 0 while the zero position is the product of the
rest; two zeros and everything is 0. It’s a special-case minefield.
3. What is the brute force wasting?
For index i and index i+1 it recomputes almost exactly the same product. The prefix for i+1
is just the prefix for i times nums[i] — one multiply, not a whole loop.
4. Optimal — two sweeps, O(1) extra space
Pass 1 (left to right): put into res[i] the product of everything strictly before i.
Pass 2 (right to left): multiply res[i] by the product of everything strictly after i,
carried in a single variable.
vector<int> productExceptSelf(vector<int>& a) {
int n = a.size();
vector<int> res(n, 1);
int prefix = 1;
for (int i = 0; i < n; i++) { res[i] = prefix; prefix *= a[i]; }
int suffix = 1;
for (int i = n - 1; i >= 0; i--) { res[i] *= suffix; suffix *= a[i]; }
return res;
}
function productExceptSelf(a) {
const n = a.length;
const res = new Array(n).fill(1);
let prefix = 1;
for (let i = 0; i < n; i++) { res[i] = prefix; prefix *= a[i]; }
let suffix = 1;
for (let i = n - 1; i >= 0; i--) { res[i] *= suffix; suffix *= a[i]; }
return res;
}
Walkthrough
nums = [1, 2, 3, 4]:
| i=0 | i=1 | i=2 | i=3 | |
|---|---|---|---|---|
| after pass 1 (left products) | 1 | 1 | 2 | 6 |
| suffix at that moment | 24 | 12 | 4 | 1 |
| final | 24 | 12 | 8 | 6 |
The visualizer below dims the region each sweep is ignoring, which makes the “two independent halves” idea concrete.
Complexity
- Time O(n) — two passes.
- Space O(1) auxiliary — one running variable; the output doesn’t count.
Traps
- Setting
res[i] = prefixafter multiplying. Order matters: write the prefix before folding ina[i], or you include yourself. - Using two extra arrays. Correct but O(n) space; the interviewer’s follow-up will be exactly this. Reuse the output.
- Overflow in C++. Products of many values exceed
intfast — check the constraints and uselong longif they allow it.
Blank re-solve prompt
Return an array where each entry is the product of all other entries. No division, O(n) time, O(1) extra space beyond the output.