Third Maximum Number: Tracking Multiple Maximums

LeetCode Third Maximum Number (problem 414) asks you to find the third distinct maximum in an integer array. If the third maximum does not exist, return the overall maximum instead. It sounds like a sorting problem at first glance, but you can solve it in a single pass with O(1) space by tracking just three variables.

Why this problem matters

This problem teaches you a technique that generalizes well: tracking the top K values in a stream of data without sorting the entire collection. You will see this same idea in problems like finding the kth largest element, tracking running medians, and maintaining top-K frequency counts. The core skill is maintaining a small set of "best so far" values as you scan through data.

The tricky part is not the algorithm itself. It is handling the edge cases cleanly. Duplicates need to be skipped. If fewer than three distinct values exist, you need to fall back to the maximum. Negative numbers and negative infinity as sentinel values can cause subtle bugs if you are not careful. This problem forces you to think about all of those details in a simple setting before you encounter them in harder problems.

Getting comfortable with the "track multiple maximums" pattern here means you will recognize it instantly when a harder problem requires the same building block.

The approach

The idea is to maintain three variables: first, second, and third, representing the three largest distinct values seen so far. Initialize all three to None (or negative infinity, depending on your preference). Then walk through the array once. For each number:

1. If it equals any of the three current maximums, skip it (no duplicates).
2. If it is greater than first, shift everything down: third = second, second = first, first = num.
3. Otherwise, if it is greater than second, shift the bottom: third = second, second = num.
4. Otherwise, if it is greater than third, just update: third = num.

After the loop, if third has been set, return it. Otherwise return first.

def third_max(nums: list[int]) -> int:
    first = second = third = None
    for num in nums:
        if num in (first, second, third):
            continue
        if first is None or num > first:
            third = second
            second = first
            first = num
        elif second is None or num > second:
            third = second
            second = num
        elif third is None or num > third:
            third = num
    return third if third is not None else first

Step-by-step walkthrough

Let's trace through nums = [2, 2, 3, 1] to see how the three tracking variables evolve, including how duplicates are handled.

Notice how the duplicate 2 at index 1 was skipped entirely. The algorithm only cares about distinct values. By the end, we have three distinct maximums (3, 2, 1), so we return the third one: 1.

Complexity analysis

The three-variable approach wins on both time and space. You scan the array once, doing a constant number of comparisons per element. No extra data structures needed.

Edge cases to watch for

• Duplicates: The array [1, 1, 2] has only two distinct values. Since there is no third distinct maximum, return the overall max (2). The continue check at the top of the loop handles this.
• Fewer than three distinct values: If the array has only one or two unique numbers, third stays None. The final check return third if third is not None else first catches this.
• Negative numbers: An array like [-1, -2, -3] works fine because we use None as our sentinel instead of a numeric value like float('-inf'). If you use negative infinity, make sure the comparison logic still works with actual negative numbers.
• All elements the same: [5, 5, 5] has only one distinct value. second and third are never set, so you return first (5).
• Large arrays with few distinct values: Performance is always O(n) regardless of how many duplicates exist, since each element involves at most three comparisons.

The building blocks

This problem relies on one core reusable pattern: tracking running extremes. You maintain a small number of variables that represent the "best values seen so far," and you update them as new data arrives.

The simplest version of this is finding a single maximum:

best = None
for num in nums:
    if best is None or num > best:
        best = num

Third Maximum Number extends that to three tracked values with a cascading update rule. The same extension works for any K: you could track the top 4, top 5, or top K values in a single pass with O(K) variables.

This pattern shows up in problems like Kth Largest Element (where a heap generalizes this idea for arbitrary K) and Top K Frequent Elements (where you track the K most common values). The difference is that for small, fixed K, you do not need a heap at all. Simple variables and if-else chains are enough.

The duplicate-skipping logic is another brick worth internalizing. Checking if num in (first, second, third) before doing any updates is the cleanest way to enforce distinctness. You will use the same "skip if already seen" guard in problems like Contains Duplicate, where a set serves the same purpose at larger scale.

From understanding to recall

You can read through this solution and understand every line in a few minutes. But understanding is not the same as recall. Two weeks from now, when you see a problem that requires tracking multiple running values, will you remember the cascading update pattern? Will you remember to check for duplicates before updating?

That is where spaced repetition makes the difference. By drilling the "track K maximums" pattern at increasing intervals, you move it from short-term comprehension into long-term muscle memory. The next time you encounter a variation of this problem, the solution structure fires automatically instead of requiring you to re-derive it from scratch.

Related posts

• Kth Largest Element - Generalizes the "find the Kth best" idea using heaps and quickselect for arbitrary K
• Contains Duplicate - Uses the same "skip duplicates" guard, applied with a hash set instead of variable tracking
• Top K Frequent Elements - Another top-K problem that combines frequency counting with selection