Third Maximum Number Solution in Python

Explore More Solutions

Code Solution


class Solution:
    def thirdMax(self, nums: list[int]) -> int:
        max1 = -math.inf  # the maximum
        max2 = -math.inf  # the second maximum
        max3 = -math.inf  # the third maximum

        for num in nums:
            if num > max1:
                max3 = max2
                max2 = max1
                max1 = num
            elif max1 > num and num > max2:
                max3 = max2
                max2 = num
            elif max2 > num and num > max3:
                max3 = num

        return max1 if max3 == -math.inf else max3

Problem Description

Ah, the classic “Third Maximum Number” problem! It’s like trying to find the third slice of pizza at a party where everyone is too busy fighting over the first two slices. You know, the one that everyone claims they don’t want, but secretly, they all do!

In this LeetCode challenge, you are given an array of integers, and your task is to find the third distinct maximum number. If it doesn’t exist, you should return the maximum number. So, if you have a list of numbers like [3, 2, 1], the third maximum is 1. But if you have [1, 2], the answer is 2 because there’s no third distinct maximum.

Approach

The code provided uses a simple yet effective approach to track the top three maximum numbers in a single pass through the list. It initializes three variables to hold the maximum, second maximum, and third maximum values. As it iterates through the list, it updates these variables based on the current number being evaluated. If a number is greater than the current maximum, it shifts the other two down the line. If it’s between the first and second maximum, it updates the second maximum, and so on.

Time and Space Complexity

Complexity	Details
Time Complexity	O(n), where n is the number of elements in the input list. We only traverse the list once.
Space Complexity	O(1), as we are using a constant amount of space for the three maximum variables.

Real-World Example

Imagine you’re at a talent show, and there are three contestants who are vying for the title of “Best Performer.” The judges are only interested in the top three performances. If the first two performances are so good that the third one is overshadowed, the judges might just declare the second performer as the winner. This is exactly what our code does—it finds the top three distinct performances (or numbers) and returns the third one if it exists.