5 Best Ways to Find the Third Maximum Number in a Python Integer List

💡 Problem Formulation: Given an integer list in Python, it is often required to find the third highest number within that list, assuming it exists. For instance, if the input is [3, 1, 2, 4, 5], the desired output is 3 because 5 is the highest, 4 is the second highest, and 3 is the third highest number.

Method 1: Sort and Select

This method involves sorting the list in descending order and selecting the third element, provided the list has at least three distinct numbers. The key function is sort(), which arranges the elements from highest to lowest, then we access the third element with the index 2.

Here’s an example:

numbers = [3, 1, 2, 4, 5]
numbers.sort(reverse=True)
third_maximum = numbers[2] if len(set(numbers)) >= 3 else "Does not exist"
print(third_maximum)

Output: 3

In this snippet, we first sort the given list in descending order, then check if there are at least three unique numbers and retrieve the third one if it exists. The strength of this method lies in its simplicity and readability, however, sorting the entire list can be inefficient for very large lists.

Method 2: Set with Sorting

First, convert the list to a set to remove duplicates, then sort the set and retrieve the third maximum number if the set’s length is greater than or equal to three. The method is efficient for lists with many duplicates as it reduces the size before sorting.

Here’s an example:

numbers = [3, 1, 1, 2, 4, 5, 5]
unique_numbers = sorted(set(numbers), reverse=True)
third_maximum = unique_numbers[2] if len(unique_numbers) >= 3 else "Does not exist"
print(third_maximum)

Output: 3

This code removes duplicates by converting the list to a set and sorts it. If the set has three or more elements, it prints the third one; otherwise, it prints “Does not exist”. This is more efficient than the first method when duplicates are present.

Method 3: Set without Sorting

The approach here is to eliminate duplicates using a set, and then apply max() three times, each time removing the max from the set. This avoids sorting but requires checking if the set has enough elements at each step.

Here’s an example:

numbers = [3, 1, 1, 2, 4, 4, 5, 5]
unique_numbers = set(numbers)
if len(unique_numbers) < 3:
    third_maximum = "Does not exist"
else:
    unique_numbers.remove(max(unique_numbers))
    unique_numbers.remove(max(unique_numbers))
    third_maximum = max(unique_numbers)
print(third_maximum)

Output: 3

This code uses a set to ensure uniqueness, then progressively finds and removes the two highest numbers and finally returns the third highest. This is more efficient than sorting large lists but can be less readable due to the multiple steps.

Method 4: Iterate with Logic

This method involves manually iterating through the list and keeping track of the top three unique numbers using variables. It’s a single-pass approach that doesn’t require sorting or converting to a set.

Here’s an example:

def third_max(numbers):
    first = second = third = float('-inf')
    for num in numbers:
        if num > first:
            third = second
            second = first
            first = num
        elif first > num > second:
            third = second
            second = num
        elif second > num > third:
            third = num
    return third if third != float('-inf') else "Does not exist"

numbers = [3, 1, 2, 4, 5]
print(third_max(numbers))

Output: 3

This function iterates through each number, updating the top three as necessary. It’s efficient for all list sizes and doesn’t create additional data structures but requires more code and careful logic consideration.

Bonus One-Liner Method 5: Using heapq

heapq module has a function nlargest() which can return the n largest elements from a dataset. In our case, we use it to fetch the top three and select the last one.

Here’s an example:

import heapq

numbers = [3, 1, 2, 4, 5]
third_maximum = heapq.nlargest(3, set(numbers))[2] if len(set(numbers)) >= 3 else "Does not exist"
print(third_maximum)

Output: 3

This one-liner uses the heapq.nlargest() function to efficiently retrieve the top three numbers from the list as a heap, after turning the list into a set to remove any duplicates. It’s a compact and efficient solution for large lists.

Summary/Discussion

Method 1: Sorting and Selecting. Simple and readable. Not optimal for very long lists.
Method 2: Remove Duplicates then Sort. Better than the first for lists with many duplicates. Still involves sorting.
Method 3: Using Sets without Sorting. Avoids sorting, but can be less intuitive due to the multiple removals.
Method 4: Iterative Logic. Most efficient. Works in a single pass without extra space. Can be complex to implement correctly.
Method 5: Using heapq. Compact one-liner. Efficient for large datasets. Relies on Python’s built-in libraries.