MediumEach answer[i] is the product of all other elements — no division, in O(n).
Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i]. The algorithm must run in O(n) time and without using the division operation.
Walkthrough
try:
answer[i] = product of every element except nums[i] — done in two passes, no division.
i=0
i=1
i=2
i=3
nums
1
2
3
4
answer
1
1
1
1
prefix = 1 →← suffix = 1
currentleft product storedfinal
1
function productExceptSelf(nums) {
2
const n = nums.length;
3
const answer = new Array(n).fill(1);
◄
4
let prefix = 1;
5
for (let i = 0; i < n; i++) {
6
answer[i] = prefix;
7
prefix *= nums[i];
8
}
9
let suffix = 1;
10
for (let i = n - 1; i >= 0; i--) {
11
answer[i] *= suffix;
12
suffix *= nums[i];
13
}
14
return answer;
15
}
answer = [1, 1, 1, 1]
step 0 / 19
line 3 · setup
Start with all 1s
answer starts as all 1s. Each answer[i] will become the product of every element EXCEPT nums[i] — and 1 is the neutral starting value for multiplication.
Intuition
The product of everything except nums[i] is just (product of everything to its LEFT) × (product of everything to its RIGHT). If you have both, you are done.
Build the left products in one forward pass: keep a running prefix and, before folding nums[i] in, store the prefix into answer[i].
Then sweep backward with a running suffix and multiply it into answer[i]. Now each cell holds left × right.
Why no division? Division would fail on zeros and is disallowed here. The two-pass prefix/suffix trick sidesteps it entirely.
The algorithm
01Fill answer with 1s.
02Forward pass: set answer[i] = prefix, then prefix *= nums[i].
03Backward pass: multiply answer[i] *= suffix, then suffix *= nums[i].
04answer now holds the product of all elements except self.
Reference implementations
1 · Prefix × suffix, O(1) extra space
Store left products in answer during a forward pass, then multiply right products in during a backward pass. This is the version animated above.
1
function productExceptSelf(nums) {
2
const n = nums.length;
3
const answer = new Array(n).fill(1);
4
let prefix = 1;
5
for (let i = 0; i < n; i++) {
6
answer[i] = prefix; // product of everything left of i
7
prefix *= nums[i];
8
}
9
let suffix = 1;
10
for (let i = n - 1; i >= 0; i--) {
11
answer[i] *= suffix; // multiply in product of everything right of i
12
suffix *= nums[i];
13
}
14
return answer;
15
}
2 · Two helper arrays (easier to read)
Keep explicit left[] and right[] arrays, then multiply them position by position. Same O(n) time but O(n) extra space — a clearer stepping stone to the optimal version.
1
function productExceptSelf(nums) {
2
const n = nums.length;
3
const left = new Array(n).fill(1); // left[i] = product before i
4
const right = new Array(n).fill(1); // right[i] = product after i
5
for (let i = 1; i < n; i++) {
6
left[i] = left[i - 1] * nums[i - 1];
7
}
8
for (let i = n - 2; i >= 0; i--) {
9
right[i] = right[i + 1] * nums[i + 1];
10
}
11
const answer = new Array(n);
12
for (let i = 0; i < n; i++) answer[i] = left[i] * right[i];
13
return answer;
14
}
Complexity
Time
O(n) — two linear passes.
Space
O(1) extra — the output array does not count; only prefix and suffix scalars are used.