# Array Of Products

Learn how to calculate the products of all array elements except the one at each index with this essential algorithm.

array
medium

Published At

3/5/2023

~ 3 min read

Write a function that takes in a non-empty array of integers and returns an array of the same length, where each element in the output array is equal to the product of every other number in the input array.

In other words, the value at output[i] is equal to the product of every number in the input array other than input[i].

Note that you're expected to solve this problem without using division.

### Sample Input

js
array = [5, 1, 4, 2]
js
array = [5, 1, 4, 2]

### Sample Output

js
[8, 40, 10, 20]
// 8 is equal to 1 x 4 x 2
// 40 is equal to 5 x 4 x 2
// 10 is equal to 5 x 1 x 2
// 20 is equal to 5 x 1 x 4
js
[8, 40, 10, 20]
// 8 is equal to 1 x 4 x 2
// 40 is equal to 5 x 4 x 2
// 10 is equal to 5 x 1 x 2
// 20 is equal to 5 x 1 x 4

### Hints

Hint 1

Think about the most naive approach to solving this problem. How can we do exactly what the problem wants us to do without focusing at all on time and space complexity?

Hint 2

Understand how output[i] is being calculated. How can we calculate the product of every element other than the one at the current index? Can we do this with just one loop through the input array, or do we have to do multiple loops?

Hint 3

For each index in the input array, try calculating the product of every element to the left and the product of every element to the right. You can do this with two loops through the array: one from left to right and one from right to left. How can these products help us

Optimal Space & Time Complexity

O(n) time | O(n) space - where n is the length of the input array

Solution-1
js
// O(n^2) time | O(n) space - where n is the length of the input array
function arrayOfProducts(array) {
let arr = []

for (let i = 0; i < array.length; i++) {
let product = 1;
let count = 0;

while (count < array.length) {
if (count !== i) {
product *= array[count]
}
count++
}

arr.push(product)
}

return arr
}
Solution-1
js
// O(n^2) time | O(n) space - where n is the length of the input array
function arrayOfProducts(array) {
let arr = []

for (let i = 0; i < array.length; i++) {
let product = 1;
let count = 0;

while (count < array.length) {
if (count !== i) {
product *= array[count]
}
count++
}

arr.push(product)
}

return arr
}
Solution-2
js
// O(n) time | O(n) space - where n is the length of the input array.
function arrayOfProducts(array) {
const products = new Array(array.length).fill(1)

let leftRunningProduct = 1;
for (let i = 0; i < array.length; i++) {
products[i] = leftRunningProduct
leftRunningProduct *= array[i]
}

let rightRunningProduct = 1;
for (let i = array.length - 1; i > -1; i--) {
products[i] *= rightRunningProduct
rightRunningProduct *= array[i];
}

return products
}
Solution-2
js
// O(n) time | O(n) space - where n is the length of the input array.
function arrayOfProducts(array) {
const products = new Array(array.length).fill(1)

let leftRunningProduct = 1;
for (let i = 0; i < array.length; i++) {
products[i] = leftRunningProduct
leftRunningProduct *= array[i]
}

let rightRunningProduct = 1;
for (let i = array.length - 1; i > -1; i--) {
products[i] *= rightRunningProduct
rightRunningProduct *= array[i];
}

return products
}

🧩

Do you have any questions, or simply wish to contact me privately? Don't hesitate to shoot me a DM on Twitter.

Have a wonderful day.
Abhishek 🙏

## Join My Exclusive Newsletter Community

Step into a world where creativity intersects with technology. By subscribing, you'll get a front-row seat to my latest musings, full-stack development resources, and exclusive previews of future posts. Each email is a crafted experience that includes:

• In-depth looks at my covert projects and musings to ignite your imagination.
• Handpicked frontend development resources and current explorations, aimed at expanding your developer toolkit.
• A monthly infusion of inspiration with my personal selection of quotes, books, and music.

Embrace the confluence of words and wonder, curated thoughtfully and sent straight to your inbox.

No fluff. Just the highest caliber of ideas.