Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].
Constraint: It’s guaranteed that the product of the elements of any prefix or suffix of the array (including the whole array) fits in a 32 bit integer.
Note: Please solve it without division and in O(n).
Example:
Input: [1,2,3,4]
Output: [24,12,8,6]
var productExceptSelf = function(nums) {
//create array of multiplication so far
let pre=[];
for (let i=0;i<nums.length;i++) {
pre[i]=(pre[i-1]===undefined ? 1 : pre[i-1]) * nums[i];
}
console.log(pre);
let post=[];
for (let i=nums.length-1;i>=0;i--) {
post[i]=(post[i+1]===undefined ? 1 : post[i+1]) * nums[i];
}
console.log(post);
let result=[];
for (let i=0;i<nums.length;i++) {
result[i]=(pre[i-1]===undefined ? 1 : pre[i-1]) * (post[i+1]===undefined ? 1 : post[i+1]);
}
console.log(result);
return result;
};
Approach:
The division would have made this a trivial problem. Start with the product of all numbers except the first, then loop through starting at second element. At each loop through, divide by the current original number and multiply by the prior number, then assign the result to the result array.
However since we can’t do that, let’s think of another way. The key here is to notice the pattern of what we’re doing at each stage. What are we doing?
At each iteration we’re taking the product of all numbers except the one we’re currently on. So for indexes 1,2,…i,…n, at each i we’re taking the product of 1,..,i-1,i+1,…n. That’s a lot of repeated calculations. How can we reduce the number of calculations? By remembering what we calculated before and saving it.
//create array of multiplication so far
let pre=[];
for (let i=0;i<nums.length;i++) {
pre[i]=(pre[i-1]===undefined ? 1 : pre[i-1]) * nums[i];
}
What if we created an array of the product so far? The length would be the same as the original array, just that at each step it’s the product of the current number and all the past numbers. We don’t have multiply all the past numbers, since we just take the current number multiplied by the previous number.
We can do the same thing by creating an array of the product of all numbers after a specific index. Here we start at the end and go backwards.
let post=[];
for (let i=nums.length-1;i>=0;i--) {
post[i]=(post[i+1]===undefined ? 1 : post[i+1]) * nums[i];
}
Now we have an array of the product of all numbers before the product and an array of the product of all numbers after the product. It’s now trivial to calculate the product excluding self since we just take the product of the two arrays at each index.
let result=[];
for (let i=0;i<nums.length;i++) {
result[i]=(pre[i-1]===undefined ? 1 : pre[i-1]) * (post[i+1]===undefined ? 1 : post[i+1]);
}
The conditional for undefined is to account for beginning and end of the loop, where we don’t have a previous index or next index to prevent overflow. Due to it being multiplicative, defaulting to 1 means it has no effect.
Solution Complexity:
The first array is a single loop through the initial array of size N, so it’s O(N). Similarly for the second and third arrays.
Time complexity is O(N) = O(3N)
Space complexity is O(N) = O(2N) not counting the original input array