This notebook was prepared by Donne Martin. Source and license info is on GitHub.

Solution Notebook

Problem: Find the highest product of three numbers in a list.

Constraints

  • Is the input a list of integers?
    • Yes
  • Can we get negative inputs?
    • Yes
  • Can there be duplicate entries in the input?
    • Yes
  • Will there always be at least three integers?
    • No
  • Can we assume the inputs are valid?
    • No, check for None input
  • Can we assume this fits memory?
    • Yes

Test Cases

  • None -> TypeError
  • Less than three ints -> ValueError
  • [5, -2, 3] -> -30
  • [5, -2, 3, 1, -1, 4] -> 60

Algorithm

Brute force:

Use three loops and multiple each numbers.

Complexity:

  • Time: O(n^3)
  • Space: O(1)

Sorting:

Sort the list, multiply the last three elements.

Complexity:

  • Time: O(n log(n))
  • Space: O(1)

Greedy:

 0   1  2  3   4  5
[5, -2, 3, 1, -1, 4] -> 60

max_prod_of_three = -30
max_prod_of_two = -10
max_num = 5
min_prod_of_two = -10
min_num = -2

 0   1  2  3   4  5
[5, -2, 3, 1, -1, 4] -> 60
        ^
max_prod_of_three = -30
max_prod_of_two = 15
max_num = 5
min_prod_of_two = -10
min_num = -2

 0   1  2  3   4  5
[5, -2, 3, 1, -1, 4] -> 60
           ^
max_prod_of_three = 15
max_prod_of_two = 15
max_num = 5
min_prod_of_two = -10
min_num = -2

 0   1  2  3   4  5
[5, -2, 3, 1, -1, 4] -> 60
               ^
max_prod_of_three = 15
max_prod_of_two = 15
max_num = 5
min_prod_of_two = -10
min_num = -2

 0   1  2  3   4  5
[5, -2, 3, 1, -1, 4] -> 60
                  ^
max_prod_of_three = 60
max_prod_of_two = 15
max_num = 5
min_prod_of_two = -10
min_num = -2

Complexity:

  • Time: O(n)
  • Space: O(1)

Code

In [1]:
class Solution(object):

    def max_prod_three_nlogn(self, array):
        if array is None:
            raise TypeError('array cannot be None')
        if len(array) < 3:
            raise ValueError('array must have 3 or more ints')
        array.sort()
        product = 1
        for item in array[-3:]:
            product *= item
        return product

    def max_prod_three(self, array):
        if array is None:
            raise TypeError('array cannot be None')
        if len(array) < 3:
            raise ValueError('array must have 3 or more ints')
        curr_max_prod_three = array[0] * array[1] * array[2]
        max_prod_two = array[0] * array[1]
        min_prod_two = array[0] * array[1]
        max_num = max(array[0], array[1])
        min_num = min(array[0], array[1])
        for i in range(2, len(array)):
            curr_max_prod_three = max(curr_max_prod_three,
                                      max_prod_two * array[i],
                                      min_prod_two * array[i])
            max_prod_two = max(max_prod_two,
                               max_num * array[i],
                               min_num * array[i])
            min_prod_two = min(min_prod_two,
                               max_num * array[i],
                               min_num * array[i])
            max_num = max(max_num, array[i])
            min_num = min(min_num, array[i])
        return curr_max_prod_three

Unit Test

In [2]:
%%writefile test_prod_three.py
import unittest


class TestProdThree(unittest.TestCase):

    def test_prod_three(self):
        solution = Solution()
        self.assertRaises(TypeError, solution.max_prod_three, None)
        self.assertRaises(ValueError, solution.max_prod_three, [1, 2])
        self.assertEqual(solution.max_prod_three([5, -2, 3]), -30)
        self.assertEqual(solution.max_prod_three([5, -2, 3, 1, -1, 4]), 60)
        print('Success: test_prod_three')


def main():
    test = TestProdThree()
    test.test_prod_three()


if __name__ == '__main__':
    main()
Overwriting test_prod_three.py
In [3]:
%run -i test_prod_three.py
Success: test_prod_three