Given an integer array nums, return an array answer such that answer[i] is the product of every element of nums except nums[i].
You must solve it without using division and in O(n) time. The product of any prefix or suffix of nums fits in a 32-bit integer.
Example
answer[0] = 2·3·4 = 24, answer[1] = 1·3·4 = 12, and so on.
Constraints
- 2 <= nums.length <= 10^5
- -30 <= nums[i] <= 30
- The product of any prefix or suffix fits in a 32-bit integer.
- Division is not allowed.
Intuition
The obvious approach computes the product of the whole array, then divides out each element to get its except-self value. But the problem forbids division (and division breaks on a zero anyway), so the honest baseline is: for each index, multiply every other element — two nested loops.
function productExceptSelf(nums) {
const answer = new Array(nums.length);
// For each slot, walk the array and multiply in every element except itself.
for (let i = 0; i < nums.length; i++) {
let product = 1;
for (let j = 0; j < nums.length; j++) {
if (j !== i) product *= nums[j]; // skip the slot we're filling
}
answer[i] = product;
}
return answer;
}This is O(n²), and division is off the table. Can we do better?
The key observation: the product of everything except nums[i] is (everything to its left) × (everything to its right). Those are a prefix product and a suffix product — the same running-accumulation idea behind Prefix sums, with multiplication instead of addition.
So do two sweeps over one output array. First left to right, writing into answer[i] the product of everything before i (a running prefix, starting at 1). Then right to left, multiplying each answer[i] by a running suffix product of everything after i. No division, O(n) time, and the only extra space is the output itself.
Walking the two passes through:
nums = [1, 2, 3, 4] · pass 1 fills prefix, pass 2 folds in suffix
Pass 1 (left→right). answer[0] = 1 (nothing to its left). Then prefix becomes 1·1 = 1.
Mid pass 1: answer = [1, 1, 2, 6-to-be]. answer[2] = 1·2 (the product of nums[0..1]).
Pass 1 complete: each slot holds the product of everything strictly to its left.
Pass 2 (right→left), suffix starts at 1. answer[3] stays 6 (nothing to its right). suffix → 4.
By the last step suffix = 2·3·4 = 24, so answer[0] = 1·24 = 24. Final: [24, 12, 8, 6].
Optimization
Prefix and suffix products
The product of everything except nums[i] is (the product of everything to its left) × (the product of everything to its right). Those are a prefix product and a suffix product — both classic running accumulations.
Do two sweeps over a single output array. First sweep left to right, writing into answer[i] the product of all elements before i (a running prefix product). Then sweep right to left, multiplying each answer[i] by a running suffix product of all elements after i. No division, O(n) time, and only the output array as extra space.
function productExceptSelf(nums) {
const n = nums.length;
const answer = new Array(n);
// Left-to-right: answer[i] = product of everything strictly before i.
let prefix = 1;
for (let i = 0; i < n; i++) {
answer[i] = prefix;
prefix *= nums[i];
}
// Right-to-left: fold in the product of everything strictly after i.
let suffix = 1;
for (let i = n - 1; i >= 0; i--) {
answer[i] *= suffix;
suffix *= nums[i];
}
return answer;
}Complexity analysis
Time complexity: O(n). Here's why:
- The left-to-right pass writes each prefix product into the output — O(n).
- The right-to-left pass folds in each suffix product — another O(n).
Two sequential linear passes give 2 × O(n) = O(n), replacing the brute force's O(n²) of multiplying all the others for each slot.
Space complexity: O(1). Here's why:
- Both prefix and suffix are tracked in single scalar accumulators, not arrays.
- The output array is required by the problem, so it isn't counted as extra space.
Beyond the output, only two running products are kept, so the extra space is O(1).
Test cases
Beyond the example above, these are worth thinking through before you submit.
| Input | Expected output | Description |
|---|---|---|
| nums = [3,4] | [4,3] | Two elements — each slot is just the other. |
| nums = [0,1,2] | [2,0,0] | One zero — only the zero's slot is non-zero. |
| nums = [0,0,5] | [0,0,0] | Two zeros — every slot becomes 0. |
| nums = [-1,2,-3] | [-6,3,-2] | Negatives — sign tracks through both passes. |
| nums = [2,2,2,2] | [8,8,8,8] | All equal — each slot is the product of the other three. |
Try it yourself
Write your solution against the real judge before checking the reference.