Product array puzzle (product of all except self)
Problem
Return an array whose ith element is the product of every element except nums[i]. Do not use division, and aim for O(n) time.
Example 1
Input: [1, 2, 3, 4] Output: [24, 12, 8, 6]
Example 2
Input: [-1, 1, 0, -3, 3] Output: [0, 0, 9, 0, 0]
Also asked as: Product array Puzzle
Test cases
Case 1
Input: [1,2,3,4] Expected: [24,12,8,6]
Case 2
Input: [-1,1,0,-3,3] Expected: [0,0,9,0,0]
Case 3
Input: [2,3] Expected: [3,2]
View solutionHide solution1 approach
1. Prefix and suffix products, no division
Time O(n)Space O(1) extra
res[i] = (product of everything left of i) · (product of everything right of i). Two passes; reuse the output array.
function productExceptSelf(a) { const n = a.length, res = Array(n).fill(1); let prefix = 1; for (let i = 0; i < n; i++) { res[i] = prefix; prefix *= a[i]; } let suffix = 1; for (let i = n - 1; i >= 0; i--) { res[i] *= suffix; suffix *= a[i]; } return res;}