highest_product_of_3

3_highest_product_of_3.rb

require "test/unit"

include Test::Unit::Assertions

# Given an array_of_ints, find the highest_product you can get from three of the integers.

# The input array_of_ints will always have at least three integers.

# First attempt. O(n log(n)) (from sort), O(1) space. Bad, though, because it didn't handle negative numbers.
# def highest_product(array_of_ints)
#   array_of_ints.sort! { |x,y| y <=> x }
#   return array_of_ints[0] * array_of_ints[1] * array_of_ints[2]
# end

# What's our complexity?
# O(n log n + 3 + 2) -> O(n log(n)).
#
# What's our space?
# O(1)
#
def highest_product(array_of_ints)
  array_of_ints.sort!

  two_lowest = array_of_ints[0..1]

  product_of_highest = array_of_ints[-3..-1].reduce(:*)

  if two_lowest.all? { |n| n < 0 }
    product_with_negatives = two_lowest.reduce(:*) * array_of_ints.last

    return product_with_negatives if product_with_negatives > product_of_highest
  end

  return product_of_highest
end


assert_equal(7 * 21 * 8, highest_product([3, 1, 7, 21, 8, 1]))
assert_equal(300, highest_product([-10, -10, 1, 3, 2]))
assert_equal(6, highest_product([-10, 1, 1, 3, 2]))
assert_equal(300, highest_product([-10, -10, 0, 3, 2]))

# What if they are all negative?
assert_equal(-12, highest_product([-10, -3, -1, -4, -6]))