The problem in my introductory computer science class asks me to find the two largest integers in a list. The list is filled only with integers and I can assume that there are at least 2 integers in the list.
The problem does not state whether the largest and second largest integers must be unique integers. In other words, if the largest integer in the list is 34 and it happens to appear twice, I will assume that 34 can be both the largest and second largest integers. The problem also does not state whether we can mutate the list. I will assume we can make destructive changes to the list. In other words, we can alter the list by adding and removing items, etc.
Max Function in Python
Given these assumptions, my first thought is the max function in Python, which will return the maximum value in a list.
integers = [1, 16, 3, 39, 26, 4, 8, 16] largest_integer = max(integers) # 39
Max is a very handy function for finding the largest integer in the list, but I also need to find the second largest integer. If I remove the largest integer from the list after finding it, then the second largest integer must now be the new largest integer. I can call max on the list a second time and get the next largest integer.
integers = [1, 16, 3, 39, 26, 4, 8, 16] largest_integer = max(integers) # 39 integers.remove(largest_integer) second_largest_integer = max(integers) # 26
If mutating the list isn't an option and assuming this is a small list of integers for the sake of computer memory, I can always clone the list and then perform the operation on the new list. This would keep the original list, integers, unmodified.
integers = [1, 16, 3, 39, 26, 4, 8, 16] # clone the list by slicing copy_of_integers = integers[:] # [1, 16, 3, 39, 26, 4, 8, 16] largest_integer = max(copy_of_integers) # 39 copy_of_integers.remove(largest_integer) second_largest_integer = max(copy_of_integers) # 26
Using the max function to find the largest and second largest integers in a list seems like an ideal solution.
Sorting the List
The other option that immediately popped into my mind was to sort the list. Once the list of integers is sorted it is really easy to pick out the largest and second largest integers. Python has a built-in sorted function that does all the work. It returns a new sorted list.
integers = [1, 16, 3, 39, 26, 4, 8, 16] sorted_integers = sorted(integers) # [1, 3, 4, 8, 16, 16, 26, 39] largest_integer = sorted_integers[-1] # 39 second_largest_integer = sorted_integers[-2] # 26
The ability to index the new sorted list using [-1] for the last item in the list and [-2] for the second-to-last item in the list is brilliant in Python. If it seems less obvious to use -1 and -2, I can sort the list in descending ( reverse ) order. When sorting in reverse the largest and second largest integers will be index 0 and 1, respectively.
integers = [1, 16, 3, 39, 26, 4, 8, 16] sorted_integers = sorted(integers, reverse=True) # [39, 26, 16, 16, 8, 4, 3, 1] largest_integer = sorted_integers # 39 second_largest_integer = sorted_integers # 26
Obviously there is overhead of sorting the list of integers, but the solution is very clean and intuitive. I like it.
Using Set to Remove Duplicates
I started thinking as to what I would do if the problem stated that the same number could not be the largest and second largest integers. In other words, they must be unique values.
One could obviously just iterate through the list until the largest two unique integers are found. However, I immediately thought of set in Python, which is guaranteed to only contain unique values. We could create a set from the list, which would remove duplicates. We could then find the two maximum values in the set using the max function.
Notice I changed the list of integers to include 39 twice, but based on the new assumption 39 cannot be both the largest and second largest integers in the list. The values must be unique, and set will eliminate redundant values for me.
integers = [1, 16, 3, 39, 26, 4, 8, 16, 39] unique_integers = set(integers) # set([1, 3, 4, 39, 8, 16, 26]) largest_integer = max(unique_integers) # 39 unique_integers.remove(largest_integer) second_largest_integer = max(unique_integers) # 26
The use of set solves the problem of uniqueness quite nicely.
Per the documentation, heapq provides an implementation of the heap queue algorithm, also known as the priority queue algorithm. It has a method, called nlargest, that can be used to find the largest 2 integers.
integers = [1, 16, 3, 39, 26, 4, 8, 16] # get 2 largest values largest_integers = heapq.nlargest(2, integers) # [39, 26] largest_integer = largest_integers # 39 second_largest_integer = largest_integers # 26
I have to say I absolutely love learning Python, which is why I beat the problem to death. I haven't looked at the answer to the problem provided by the instructor in the course, but I will later today :) I highly recommend taking advantage of free online training. I have learned a lot about algorithms, data structures, and Python programming thanks to a lot of wonderful online resources.
Posted by Koder Dojo
I am a freelance C# ASP.NET MVC Developer currently learning data structures and algorithms using the Python programming language. Many of my blog posts are based on problem sets and exercises from the various Python and Computer Science courses I am attending online. If you are learning Python or programming, I hope my code samples help or inspire you.