238. Product of Array Except Self 🔗
Date: Jun 03, 2024
Tags: prefix-sum
Description
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 product of any prefix or suffix of nums
is
guaranteed to fit in a
32-bit integer.
You must write an algorithm that runs
in O(n)
time and without using the division
operation.
Example 1:
Input: nums = [1,2,3,4] Output: [24,12,8,6]
Example 2:
Input: nums = [-1,1,0,-3,3] Output: [0,0,9,0,0]
Constraints:
-
2 <= nums.length <= 105
-
-30 <= nums[i] <= 30
-
The product of any prefix or suffix of
nums
is guaranteed to fit in a 32-bit integer.
Follow up: Can you solve the problem in
O(1)
extra space complexity? (The output array
does not count as extra space for space
complexity analysis.)
Optimal
function productExceptSelf(nums: number[]): number[] {
const len = nums.length;
const result: number[] = Array(len).fill(1);
let x = 1;
for (let i = 0; i < len; i++) {
result[i] = x;
x *= nums[i];
}
x = 1;
for (let i = len - 1; i >= 0; i--) {
const product = result[i] * x;
result[i] = Object.is(-0, product) ? 0 : product;
x *= nums[i];
}
return result;
}
export { productExceptSelf };
Brute-Force
function productExceptSelf(nums: number[]): number[] {
const result: number[] = Array.from({ length: nums.length }).map(() => 1);
for (let i = 0; i < nums.length; i++) {
for (let j = 0; j < nums.length; j++) {
if (i !== j) {
result[i] *= nums[j];
}
}
}
return result.map((x) => (Object.is(-0, x) ? 0 : x));
}
export { productExceptSelf };