Product array puzzle (product of all except self)

Medium

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]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}