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 — InterviewCake

This problem is straight outta InterviewCake. Attempted to solve it but got stuck and eventually looked into the solution. Sadly, the solution wasn’t visual enough for me, although it was pretty descriptive. As a visual learner, I couldn’t stop but write this post with some visuals that are just some neat versions of the ones I jotted down on my notebook!

Here goes some more description on the problem:

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]

Here’s the catch: You can’t use division in your solution!

Notice that, doing it with division would be an easy cake! We could basically multiply all the numbers in O(n). and then divide by that product by the item at the current index. Sadly, we can’t do that.

We need to think cleverly!

The Pattern

Let’s take a closer look at our I/O:

Input: [1, 7, 3, 4]

Output: [84, 12, 28, 21]

Breakdown of Output: [7 * 3 * 4, 1 * 3 * 4, 1 * 7 * 4, 1 * 7 * 3]

Notice that for every item at each index there are two portions => the numbers before that index and the numbers after that index. This would be the key to unlocking the solution.

For example:

output[0] = [7 * 3 * 4]

here, all the numbers are after input[0]

output[1] = [1 * 3* 4]

here, [1] is before and [3, 4] is after input[1]

output[2] = [1 * 7 * 4]

here, [1, 7] is before and [4] is after input[2]

so, the bottom line is if we could generate a list of the before and after products of the number at a particular index then multiply each parallelly we could get the correct output list.

Visuals