prefix →
pass
For each position, you need the product of every other element — but division is forbidden. Two sweeps over the array (one left-to-right accumulating a prefix product, one right-to-left accumulating a suffix product) give every answer in O(n) time with O(1) extra space.
Given an integer array nums, return an array output where output[i] equals the product of every element in nums except nums[i]. You may not use division, and the solution must run in O(n) time. For example: [1, 2, 3, 4] → [24, 12, 8, 6] (index 0 gets 2×3×4=24, index 1 gets 1×3×4=12, and so on).
nums[i] equals (product of nums[0..i-1]) × (product of nums[i+1..n-1]) — a left prefix and a right suffix. Sweep left-to-right to fill the prefix into res, then sweep right-to-left multiplying in the suffix. No division, no extra array — just two running accumulators.res[n] initialized to 1. This is the only array; it's the answer array so it does not count against the O(1) extra-space requirement.prefix = 1. For each i from left to right: write res[i] = prefix, then prefix *= nums[i]. After this pass, res[i] holds the product of everything to the left of i.suffix = 1. For each i from right to left: res[i] *= suffix, then suffix *= nums[i]. This folds in the product of everything to the right — the slot now holds prefix × suffix.res. No intermediate arrays, no division, two linear passes.res[i] must be the product of elements before i, not including it. The update prefix *= nums[i] must come after the write, not before. Swapping those two lines gives the wrong answer — every prefix will include nums[i] itself.If division were permitted you'd compute the total product, then divide by each element — but that breaks on zeros and the problem explicitly bans it.
[1, 2, 3, 4]. We build res without division. First pass: left-to-right prefix products.function productExceptSelf(nums: number[]): number[] {
const n = nums.length;
const res: number[] = new Array(n).fill(1);
// Pass 1 — left to right: res[i] = product of nums[0..i-1]
let prefix = 1;
for (let i = 0; i < n; i++) {
res[i] = prefix;
prefix *= nums[i];
}
// Pass 2 — right to left: multiply res[i] by product of nums[i+1..n-1]
let suffix = 1;
for (let i = n - 1; i >= 0; i--) {
res[i] *= suffix;
suffix *= nums[i];
}
return res;
}1means any suffix or prefix multiply that hasn't happened yet contributes nothing — a safe identity element.res[i] is set to the running prefix before nums[i] is folded in. The update order is critical: write first, multiply second. After this loop, res[i] = nums[0] × nums[1] × … × nums[i-1].res[i] *= suffix fires before suffix *= nums[i] for the same reason — we want everything after i, not including i. The product stored is now left × right = answer.res[i]— but since division is banned in this problem, you'd cross-reference the original array instead.left[] array and suffix sums in right[], then multiply. Same O(n) time but O(n) extra space. The single-array version is strictly better.| "product of all except nums[i]" | prefix × suffix accumulators |
| no division allowed | two-pass prefix/suffix into output array |
| "max/min/sum on both sides of index i" | prefix pass + suffix pass pattern |
| O(1) space constraint on array problem | store state in the output array |
function productExceptSelf(nums: number[]): number[] {
const n = nums.length;
const res = new Array<number>(n).fill(1);
let prefix = 1;
for (let i = 0; i < n; i++) {
res[i] = prefix;
prefix *= nums[i];
}
let suffix = 1;
for (let i = n - 1; i >= 0; i--) {
res[i] *= suffix;
suffix *= nums[i];
}
return res;
}i: nums[0] × … × nums[i-1]. Index 0 holds 1 (empty product).nums = [1, 2, 3, 4], what is res[2] in the final output?[2, 3, 4, 5]. After the left pass only, what is res?