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.

From HackerEarth’s Big O Cheatsheet

There Has to Be a Better Way!

D’oh! So much failure!

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.