A Common-Sense Guide to Data Structures and Algorithms in Python, Volume 1

Chapter 13

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

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