Product of Array Except Self
MediumArrays and hashing
For each position i in nums, multiply together every other number in the array, leaving out nums[i] itself. Return those products as an array in the same order.
Do it in O(n) time without using division.
Examples
Input: nums = [2, 3, 4, 5] Output: [60, 40, 30, 24]
answer[0] is 3 × 4 × 5 = 60, answer[1] is 2 × 4 × 5 = 40, and so on.
Input: nums = [3, 0, -2, 4] Output: [0, -24, 0, 0]
Every product but the one that leaves out the 0 is 0; that one is 3 × -2 × 4 = -24.
Constraints
2 ≤ nums.length ≤ 10⁵-30 ≤ nums[i] ≤ 30- Every product of a run of numbers from the start or from the end fits in a 32-bit integer.
Stuck?
Hint 1
The product of everything except nums[i] is the product of everything to its left times the product of everything to its right.
Hint 2
Fill the answer with left products in one pass, then walk back from the end with a running right product and multiply it in.
The idea
Everything except nums[i] splits into the numbers to its left and the numbers to its right. One pass from the left gives each position the product of what comes before it, and one pass from the right multiplies in the product of what comes after. There is no division, so a zero in the array causes no trouble.
Time O(n)Extra space O(1) besides the answer
Try it again with the idea in mind, or go through the code one step at a time.
The code, step by step
Step 1 of 4
The answer array also holds the work in progress, which is why no other array is needed and the extra space stays constant.
function productExceptSelf(nums) { const answer = new Array(nums.length).fill(1); let left = 1; for (let i = 0; i < nums.length; i++) { answer[i] = left; left *= nums[i]; } let right = 1; for (let i = nums.length - 1; i >= 0; i--) { answer[i] *= right; right *= nums[i]; } return answer;}The trap
Dividing the product of the whole array by nums[i] gives the right answer whenever the array has no zero. With a zero in it, the total is 0, so the zero's own position works out 0 / 0. In JavaScript that is NaN, which the test result shows as null, where the answer is the product of all the other numbers.
function productExceptSelf(nums) { const total = nums.reduce((product, n) => product * n, 1); return nums.map((n) => total / n); // divides by zero when nums holds a 0}