A solution to LeetCode Problem 238. Product of Array Except Self in JavaScript
If you’re preparing for technical interviews or want to improve your coding skills, solving practice problems on LeetCode is a great way.
In this post, we’ll discuss a solution to the “238. Product of Array Except Self” problem on LeetCode.
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
numsis guaranteed to fit in a 32-bit integer.
Solution:
- One solution to this problem is to use a brute force approach, where we loop through the array and for each element, we compute the product of all the other elements in the array. This solution has a time complexity of O(n^2) and is not efficient for large inputs.
- A better solution is to use a two-pass approach. We can use a left array left and a right array right to store the product of all the elements to the left and right of each element, respectively. Then, we can loop through the array and for each element, we can compute the product of the elements in the left and right arrays at the corresponding indices.
Here is the pseudocode for this approach:
left[0] = 1
for i = 1 to n–1
left[i] = left[i–1] * nums[i–1]
right[n–1] = 1
for i = n–2 to 0
right[i] = right[i+1] * nums[i+1]
for i = 0 to n–1
output[i] = left[i] * right[i]
return output
This solution has a time complexity of O(n) and a space complexity of O(n), which is much more efficient than the brute force approach.
Here is the code in JavaScript:
function productExceptSelf(nums) {
const n = nums.length;
const left = new Array(n);
const right = new Array(n);
const output = new Array(n);
left[0] = 1;
for (let i = 1; i < n; i++) {
left[i] = left[i – 1] * nums[i – 1];
}
right[n – 1] = 1;
for (let i = n – 2; i >= 0; i–) {
right[i] = right[i + 1] * nums[i + 1];
}
for (let i = 0; i < n; i++) {
output[i] = left[i] * right[i];
}
return output;
}
I hope this helps! Let me know if you have any questions or suggestions for improvement.