You have a list of integers, and for each index you want to find the product of every integer except the integer at that index.

Write a function get_products_of_all_ints_except_at_index() that takes a list of integers and returns a list of the products.

For example, given:

[1, 7, 3, 4]

your function would return:

[84, 12, 28, 21]

by calculating:

[7*3*4, 1*3*4, 1*7*4, 1*7*3]

Do not use division in your solution.

Gotchas

Does your function work if the input list contains zeroes? Remember—no division.

We can do this in O(n) time and O(n) space!

We only need to allocate one new list of size nn.

Breakdown

A brute force approach would use two loops to multiply the integer at every index by the integer at every nested_index, unless index == nested_index.

This would give us a runtime of O(n^2). Can we do better?

Well, we’re wasting a lot of time doing the same calculations. As an example, let's take:

# input list
[1, 2, 6, 5, 9]

# list of the products of all integers
# except the integer at each index:

[540, 270, 90, 108, 60] # [2*6*5*9, 1*6*5*9, 1*2*5*9, 1*2*6*9, 1*2*6*5]

We're doing some of the same multiplications two or three times!

When we calculate [2*6*5*9, 1*6*5*9, 1*2*5*9, 1*2*6*9, 1*2*6*5], we're calculating 5*9 three times: at indices 0, 1, and 2.

Or look at this pattern:

When we calculate [2*6*5*9, 1*6*5*9, 1*2*5*9, 1*2*6*9, 1*2*6*5], we have 1 in index 1, and we calculate 1*2 at index 2, 1*2*6 at index 3, and 1*2*6*5 at index 4.

We’re redoing multiplications when instead we could be storing the results! This would be a great time to use a greedy ↴ approach. We could store the results of each multiplication highlighted in blue, then just multiply by one new integer each time.

So in the last highlighted multiplication, for example, we wouldn’t have to multiply 1*2*6 again. If we stored that value (12) from the previous multiplication, we could just multiply 12*5.

Can we break our problem down into subproblems so we can use a greedy approach?

Let's look back at the last example:

When we calculate [2*6*5*9, 1*6*5*9, 1*2*5*9, 1*2*6*9, 1*2*6*5], we have 1 in index 1, and we calculate 1*2 at index 2, 1*2*6 at index 3, and 1*2*6*5 at index 4.

What do all the highlighted multiplications have in common?

They are all the integers that are before each index in the input list ([1, 2, 6, 5, 9][1,2,6,5,9]). For example, the highlighted multiplication at index 3 (1261∗2∗6) is all the integers before index 3 in the input list.

In the pattern where we calculate 12 at index 2, 126 at index 3, and 1265 at index 4, each calculation is the product of all the numbers before the number at that index. For example, 5 is at index 3, and 126 is the product of all the numbers before 5 in the input array.

Do all the multiplications that aren't highlighted have anything in common?

Yes, they're all the integers that are after each index in the input list!

Knowing this, can we break down our original problem to use a greedy approach?

The product of all the integers except the integer at each index can be broken down into: