# 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

| Item | Meaning |
|---|---|
| Input | Integer array `nums` |
| Output | Third distinct maximum, or maximum if fewer than three distinct values |
| Duplicate rule | Equal values count once |
| Return type | Integer |

Example function shape:

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

## Examples

Example 1:

```python
nums = [3, 2, 1]
```

The distinct values in descending order are:

```python
3, 2, 1
```

The third maximum is:

```python
1
```

So the answer is:

```python
1
```

Example 2:

```python
nums = [1, 2]
```

There are only two distinct values:

```python
2, 1
```

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

```python
2
```

Example 3:

```python
nums = [2, 2, 3, 1]
```

The distinct values are:

```python
3, 2, 1
```

The two copies of `2` count as one distinct value.

So the third maximum is:

```python
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:

```python
values = sorted(set(nums))
```

Then:

```python
values[-3]
```

is the third largest if it exists.

This is simple, but sorting costs:

```python
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:

| Variable | Meaning |
|---|---|
| `first` | Largest distinct number seen so far |
| `second` | Second largest distinct number seen so far |
| `third` | Third largest distinct number seen so far |

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:

```python
third = second
second = first
first = num
```

If it is between `first` and `second`, then:

```python
third = second
second = num
```

If it is between `second` and `third`, then:

```python
third = num
```

## Algorithm

Initialize:

```python
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

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | We scan the array once |
| Space | `O(1)` | We store only three values |

Here `n` is the length of `nums`.

## Implementation

```python
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:

```python
first = None
second = None
third = None
```

This avoids bugs with the minimum 32-bit integer:

```python
-2**31
```

The duplicate check is necessary:

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

Without this check, an input like:

```python
[2, 2, 3, 1]
```

could incorrectly treat duplicate `2`s as different maximums.

When a new largest number appears:

```python
third = second
second = first
first = num
```

The old values shift down by one rank.

When a number belongs in second place:

```python
third = second
second = num
```

When it belongs in third place:

```python
third = num
```

Finally:

```python
return third if third is not None else first
```

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

## Testing

```python
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

| Test | Why |
|---|---|
| `[3,2,1]` | Exactly three distinct values |
| `[1,2]` | Fewer than three distinct values |
| `[2,2,3,1]` | Duplicates must be ignored |
| `[1,2,2,5,3,5]` | Mixed duplicates and unordered values |
| Negative values | Works below zero |
| Minimum 32-bit integer | Avoids sentinel-value bug |
| All duplicates | Returns the only maximum |