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

# Solution Notebook¶

## 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