LeetCode 414: Third Maximum Number

Problem Restatement

We are given an integer array nums.

Return the third distinct maximum number in the array.

If the array does not contain three distinct numbers, return the maximum number.

Duplicates do not count as separate maximums.

The problem statement says to return the third distinct maximum number, or the maximum number if the third maximum does not exist. The constraints include 1 <= nums.length <= 10^4 and -2^31 <= nums[i] <= 2^31 - 1.

Input and Output

Example function shape:

def thirdMax(nums: list[int]) -> int:
    ...

Examples

Example 1:

nums = [3, 2, 1]

The distinct values in descending order are:

3, 2, 1

The third maximum is:

1

So the answer is:

1

Example 2:

nums = [1, 2]

There are only two distinct values:

2, 1

The third maximum does not exist, so we return the maximum:

2

Example 3:

nums = [2, 2, 3, 1]

The distinct values are:

3, 2, 1

The two copies of 2 count as one distinct value.

So the third maximum is:

1

First Thought: Sort Unique Values

A simple approach is:

1. Convert nums to a set to remove duplicates.
2. Sort the distinct values.
3. If there are at least three values, return the third largest.
4. Otherwise, return the largest.

Code idea:

values = sorted(set(nums))

Then:

values[-3]

is the third largest if it exists.

This is simple, but sorting costs:

O(n log n)

We can do better because we only need the top three distinct values.

Key Insight

We only need to remember three numbers:

As we scan the array, each new distinct number can affect one of these three positions.

If a number is already equal to one of them, we skip it because duplicates do not count.

If it is larger than first, then all three values shift down:

third = second
second = first
first = num

If it is between first and second, then:

third = second
second = num

If it is between second and third, then:

third = num

Algorithm

Initialize:

first = None
second = None
third = None

For each num in nums:

1. If num is already equal to first, second, or third, skip it.
2. If first is empty or num > first, shift values down and update first.
3. Else if second is empty or num > second, shift second down and update second.
4. Else if third is empty or num > third, update third.

At the end:

1. If third exists, return third.
2. Otherwise, return first.

Correctness

After processing any prefix of the array, first, second, and third store the largest three distinct values seen so far, in descending order, when those values exist.

Initially, no values have been processed, so the claim holds.

When a new number is processed, duplicates are skipped. This is correct because equal values do not change the set of distinct maximums.

For a new distinct value, there are four cases.

If it is greater than first, it becomes the largest value, and the old first and second become the second and third values.

If it is between first and second, it becomes the second largest value, and the old second becomes the third.

If it is between second and third, it becomes the third largest value.

If it is smaller than or equal to third, it cannot affect the largest three distinct values.

Thus the invariant remains true after every number.

After the full array is processed, if third exists, it is the third distinct maximum. If it does not exist, fewer than three distinct numbers were found, so the correct answer is the maximum value, first.

Complexity

Here n is the length of nums.

Implementation

from typing import List, Optional

class Solution:
    def thirdMax(self, nums: List[int]) -> int:
        first: Optional[int] = None
        second: Optional[int] = None
        third: Optional[int] = None

        for num in nums:
            if num == first or num == second or num == 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

Code Explanation

We use None instead of a numeric sentinel:

first = None
second = None
third = None

This avoids bugs with the minimum 32-bit integer:

-2**31

The duplicate check is necessary:

if num == first or num == second or num == third:
    continue

Without this check, an input like:

[2, 2, 3, 1]

could incorrectly treat duplicate 2s as different maximums.

When a new largest number appears:

third = second
second = first
first = num

The old values shift down by one rank.

When a number belongs in second place:

third = second
second = num

When it belongs in third place:

third = num

Finally:

return third if third is not None else first

If we found three distinct values, return the third. Otherwise, return the maximum.

Testing

def test_third_max():
    s = Solution()

    assert s.thirdMax([3, 2, 1]) == 1
    assert s.thirdMax([1, 2]) == 2
    assert s.thirdMax([2, 2, 3, 1]) == 1
    assert s.thirdMax([1, 2, 2, 5, 3, 5]) == 2
    assert s.thirdMax([-1, -2, -3]) == -3
    assert s.thirdMax([-2147483648, 1, 2]) == -2147483648
    assert s.thirdMax([1, 1, 1]) == 1

    print("all tests passed")

Test Notes