Chapter 13

These are the solutions to the exercises found in the section .

1. If we sort the numbers, we know that the three greatest numbers will be at the end of the array, and we can just multiply them together. The sorting will take O(N log N):

   ​	​def​ ​greatest_product_of_3​(array):
   ​	array.sort()
   ​
   ​	​return​ array[-1] * array[-2] * array[-3]

   (This code takes for granted that there are at least three values in the array. You can add code to handle arrays where this is not the case.)

2. If we presort the array, we can then expect each number to be at its own index. That is, the 0 should be at index 0, the 1 should be at index 1, and so on. We can then iterate through the array looking for a number that doesn’t equal the index. Once we find it, we know that we just skipped over the missing number:

   ​	​def​ ​find_missing_number​(array):
   ​	array.sort()
   ​
   ​	​for​ index, num ​in​ enumerate(array):
   ​	​if​ num != index:
   ​	​return​ index
   ​
   ​	​return​ None

   The sorting takes N log N steps, and the loop afterward takes N steps. However, we reduce the expression (N log N) + N to O(N log N) since the added N is a lower order compared to N log N.

3. This implementation uses nested loops and is O(N²):

   ​	​def​ ​max​(array):
   ​	​if​ ​not​ array:
   ​	​return​ None
   ​
   ​	​for​ i ​in​ array:
   ​	i_is_greatest_number = True
   ​
   ​	​for​ j ​in​ array:
   ​	​if​ j > i:
   ​	i_is_greatest_number = False
   ​
   ​	​if​ i_is_greatest_number:
   ​	​return​ i

   The next implementation simply sorts the array and returns the last number. The sorting is O(N log N):

   ​	​def​ ​max​(array):
   ​	​if​ ​not​ array:
   ​	​return​ None
   ​
   ​	array.sort()
   ​
   ​	​return​ array[-1]

   Our next and final implementation is O(N), since we iterate just once over the array:

   ​	​def​ ​max​(array):
   ​	​if​ ​not​ array:
   ​	​return​ None
   ​
   ​	greatest_number_so_far = array[0]
   ​
   ​	​for​ number ​in​ array:
   ​	​if​ number > greatest_number_so_far:
   ​	greatest_number_so_far = number
   ​
   ​	​return​ greatest_number_so_far