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.
Solution:
Time Complexity : O(n)
Space Complexity: O(n)
var productExceptSelf = function(nums) {
// Value to increment per each index
let carry = 1
// Array to return all the product values
const output = Array(nums.length).fill(1)
// Add products to output array starting at the front
for(let i = 0; i < nums.length;i++){
output[i]*=carry
carry*=nums[i]
}
// Reset carry
carry = 1
// Add products to output array starting at the back
for(let i = nums.length-1; i >= 0; i--){
output[i]*=carry
carry*=nums[i]
}
return output
};
Top comments (2)
Brilliant soluton. absolutely loved it. My solution was about 70 lines, a little difficult to understand and is faster than only 10 % submissions and this one is just about 20 lines and so easy to understand and is faster than 70% submissions. I created an account here just to thank you for this.
I get negative zeros for this, ie. does not pass test case:
Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]