Product of Array Except Self
Receives an array of integers and returns a new array of the same length where every position holds the product of all the other elements — never its own. It avoids division entirely (so a zero anywhere in the input needs no special case) by building two auxiliary arrays: a left-to-right pass fills prefix[i] with the product of everything strictly left of i, and a right-to-left pass fills suffix[i] with the product of everything strictly right of i, both seeded with 1 because the empty product is 1. A final pass multiplies the two per index, since everything except element i is exactly everything to its left times everything to its right. It runs in linear time; the caller's array is never mutated, an empty input returns an empty array, and a single element returns [1].
Visualization
- Input
- Result
Algorithm code
// Product of Array Except Self — a single pure function. Receives an array of
// integers and returns an array where every position holds the product of all
// the other elements, computed without division. Two auxiliary arrays record,
// for each index, the product of everything strictly to its left and of
// everything strictly to its right; the answer is the product of those two.
/**
* @param {number[]} nums - the integers to combine
* @returns {number[]} array whose i-th entry is the product of every nums[j], j !== i
*/
export function productExceptSelf(nums) {
const n = nums.length;
if (n === 0) {
return [];
}
const prefix = new Array(n);
prefix[0] = 1;
for (let i = 1; i < n; i += 1) {
prefix[i] = prefix[i - 1] * nums[i - 1];
}
const suffix = new Array(n);
suffix[n - 1] = 1;
for (let i = n - 2; i >= 0; i -= 1) {
suffix[i] = suffix[i + 1] * nums[i + 1];
}
const result = new Array(n);
for (let i = 0; i < n; i += 1) {
result[i] = prefix[i] * suffix[i];
}
return result;
}FUNCTION productExceptSelf(nums):
n ← length(nums)
IF n = 0:
RETURN []
prefix ← new array of size n
prefix[0] ← 1
FOR i FROM 1 TO n - 1:
prefix[i] ← prefix[i - 1] × nums[i - 1]
suffix ← new array of size n
suffix[n - 1] ← 1
FOR i FROM n - 2 DOWNTO 0:
suffix[i] ← suffix[i + 1] × nums[i + 1]
result ← new array of size n
FOR i FROM 0 TO n - 1:
result[i] ← prefix[i] × suffix[i]
RETURN result