# Products of an Array

More algorithm fun today, here’s our problem courtesy of Interview Cake. Mmm, cake.

Given an array of numbers, for each index find the product of every integer except the integer at that index.

For example, we’re given:

[1, 7, 3, 4]

Our method needs to calculate the products like this:

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

Which results in:

[84, 12, 28, 21]

Sounds simple enough, right? Well, there’re 2 pretty big limitations:

The first, we** can’t use division**. Otherwise we’d simply be able to find the product of the entire array then divide by each element.

arr = [1, 7, 3, 4]

product = arr.inject(:*)

result = []

arr.each_with_index do |value, index|

result[index] = product / value

end

result

And second, we’ll need to **account for an input array containing any zeros**. Multiplying by zero equals zero, so if we add a zero (or two) to our array we don’t want to end up with a bunch of zeros.

arr = [1, 7, 0, 3, 4]

7 * 0 * 3 * 4 = big fat zero

### A Basic Solution

A pretty simple solution would be nested each statements where we skip the inner iteration if it means multiplying the current element into the product (or if the current element is 0):

arr = [1, 7, 0, 3, 4]

result = []

arr.each do |value|

result << 1

arr.each do |value2|

next if value2 == 0 || value == value2

result[-1] *= value2

end

end

result

That quite nicely takes care of the problem’s limitations. However it uses a nested loop, which means the **time complexity of this solution is O(n²)**. The bigger our input array gets, the longer it will take since we are completely iterating through our every element for every element in the array — overall, pretty inefficient.

### There Has to Be a Better Way!

We can instead split our array and iterate over it from the left and the right. As we go, we’ll find the product of those elements we’re going through, then find the product of the left and right products.

n = arr.length

result = []

left = 1 # temp value for finding products

index = 0 # iterate from the left

while index < n do

result[index] = left

left *= arr[index] unless arr[index] == 0

index += 1

end

right = 1 # temp value for finding products

index = n - 1 # iterate from the right

while index >= 0 do

result[index] *= right

right *= arr[index] unless arr[index] == 0

index -= 1

end

result

While not as elegant overall (this solution gives us more lines and some repetition) we’ll **reduce our time complexity to O(n)**. We do iterate over the array twice which actually gives us O(2n), but we can drop the 2 because it’s a constant input.