Problem Description

Given a non-empty array of integers called nums, your task is to return the third distinct maximum number in this array. If the third maximum does not exist, return the maximum number instead.

• Each element in nums may appear more than once, but only distinct values are considered for the "third maximum".
• If there are fewer than three distinct numbers, return the largest number in the array.
• The array may contain negative numbers and duplicates.

Key Constraints:

• All elements are integers.
• The array is non-empty.
• Do not reuse elements for different maximums.

Thought Process

When facing this problem, the first idea might be to sort the array and pick the third largest value. However, since duplicates do not count as distinct maximums, simply sorting and picking the third element from the end could be incorrect if there are repeated numbers.

To handle duplicates, we need a way to keep track of only unique values. This suggests using a data structure that automatically ignores duplicates, such as a set. After collecting all unique numbers, we can sort or otherwise determine the top three.

To optimize, we can avoid sorting the entire array by keeping track of the top three unique values as we iterate. This way, we don't waste time sorting values we don't need.

Solution Approach

Let's break down the optimized approach step by step:

1. Use a Set for Uniqueness: As we traverse the array, we want to consider each number only once. Using a set helps us ignore duplicates.
2. Track Top Three Maximums: We can maintain three variables (let's call them first, second, and third) to store the highest, second highest, and third highest unique numbers seen so far.
3. Iterate and Update: For each number, check if it is already one of the top three. If not, compare and update the positions accordingly:
   • If the number is greater than first, shift all values down and set first to this number.
   • If it falls between first and second, update second and shift third down.
   • If it falls between second and third, update third.
4. Return the Result: If third was updated (i.e., we found three distinct maximums), return it. Otherwise, return first (the maximum).

This approach ensures we only keep track of what matters and never waste time sorting the entire list.

Example Walkthrough

Let's consider the input nums = [2, 2, 3, 1].

1. Initialize: first = None, second = None, third = None
2. Iterate:
   • First number: 2 → first = 2
   • Second number: 2 (duplicate) → ignore
   • Third number: 3 → first = 3, second = 2
   • Fourth number: 1 → third = 1
3. Now, first = 3, second = 2, third = 1. All three are filled, so we return 1 (the third maximum).

If the input was [1, 2], after processing we'd have first = 2, second = 1, but third would still be None. Thus, we'd return 2 (the maximum).

Time and Space Complexity

Brute-force Approach:

• Sort the array and remove duplicates: O(n \log n)
• Pick the third element from the end.
• Space: O(n) for storing unique elements.

• Single pass through the array: O(n)
• Constant space for three variables, plus O(n) for the set (if using a set for uniqueness).

The optimized approach is faster because it avoids sorting and only keeps track of the top three unique maximums.

Summary

The key to solving the "Third Maximum Number" problem efficiently is to focus only on unique values and keep track of just the top three as we iterate. By using a set to filter duplicates and carefully updating our three maximum variables, we avoid unnecessary computation and achieve optimal performance. This elegant approach demonstrates the power of combining simple data structures with thoughtful iteration.

Code Implementation

class Solution:
    def thirdMax(self, nums):
        first = second = third = 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
      

class Solution {
public:
    int thirdMax(vector<int>& nums) {
        long first = LONG_MIN, second = LONG_MIN, third = LONG_MIN;
        for (int num : nums) {
            if (num == first || num == second || num == third) continue;
            if (num > first) {
                third = second;
                second = first;
                first = num;
            } else if (num > second) {
                third = second;
                second = num;
            } else if (num > third) {
                third = num;
            }
        }
        return third == LONG_MIN ? first : third;
    }
};
      

class Solution {
    public int thirdMax(int[] nums) {
        Long first = null, second = null, third = null;
        for (int num : nums) {
            if ((first != null && num == first) || 
                (second != null && num == second) || 
                (third != null && num == third)) {
                continue;
            }
            if (first == null || num > first) {
                third = second;
                second = first;
                first = (long) num;
            } else if (second == null || num > second) {
                third = second;
                second = (long) num;
            } else if (third == null || num > third) {
                third = (long) num;
            }
        }
        return third == null ? first.intValue() : third.intValue();
    }
}
      

var thirdMax = function(nums) {
    let first = null, second = null, third = null;
    for (let num of nums) {
        if (num === first || num === second || num === third) continue;
        if (first === null || num > first) {
            third = second;
            second = first;
            first = num;
        } else if (second === null || num > second) {
            third = second;
            second = num;
        } else if (third === null || num > third) {
            third = num;
        }
    }
    return third === null ? first : third;
};