Solution: Third Maximum Number

Statement

For a given integer array nums, your task is to return the third maximum distinct number in the array. If there are fewer than three distinct numbers, return the maximum number.

Constraints:

• $1 <=$ nums.length $<= 10^3$

• $-2^{31} <=$nums[i] $<= 2^{31}-1$

Solution

The solution uses a min heap to track the list’s top three maximum numbers. A set ensures that only distinct numbers are considered. The approach keeps a rolling set of the top three numbers, updating it as larger numbers are encountered and ensuring no duplicates are included.

Now, let’s walk through the steps of the solution:

1. We create a min heap, heap, to store the top three distinct numbers.

2. We also create a set, taken to store numbers that have already been added to the heap, ensuring we only push distinct numbers into the heap.

3. We iterate through the nums list, and for each element in the list, we check if it has already been added to the taken set:

   1. If it has, we skip that element.

   2. If it hasn’t, we proceed to check the length of the heap:

      1. If the heap has less than three numbers, we push the current number into the heap and add it to the taken set.

      2. If the heap already contains three numbers and the current number is larger than the smallest number in the heap (the root of the heap), we remove the smallest number, update the taken set, and push the current number into the heap.

4. We also handle special cases where the list has fewer than three distinct numbers:

   1. After processing all the numbers, we check the size of the heap:

      1. If the heap contains only one number, we return that number since it’s the only distinct maximum.

      2. If the heap contains two distinct numbers, we return the larger of the two.

5. If the heap contains three distinct numbers, we return the smallest number from the heap, which will be the third maximum distinct number.

Let’s look at the following illustration to get a better understanding: