Problem Description

You are given an integer array nums. Your task is to find and return the third distinct maximum number in this array.

The key requirements are:

• The number must be the third largest distinct value (duplicates don't count as separate maximums)
• If there aren't three distinct numbers in the array, return the maximum number instead

For example:

• If nums = [3, 2, 1], the three distinct numbers are 3, 2, and 1, so the third maximum is 1
• If nums = [1, 2], there are only two distinct numbers, so we return the maximum which is 2
• If nums = [2, 2, 3, 1], the distinct numbers are 3, 2, and 1 (the duplicate 2 is ignored), so the third maximum is 1

The solution tracks the three largest distinct values using variables m1, m2, and m3 representing the first, second, and third maximum respectively. It processes each number in the array once, updating these maximums as needed while skipping duplicates. The cascading update pattern (shifting values down when a new maximum is found) ensures the three variables always hold the three largest distinct values seen so far.

Intuition

The natural approach to finding the third maximum would be to sort the array, remove duplicates, and return the third element. However, this would require O(n log n) time for sorting. Can we do better?

Since we only need to track the top 3 distinct values, we don't need to maintain the entire sorted order. Think of it like having three podium positions - gold, silver, and bronze. As we scan through the array, we only need to update these three positions when we encounter a new contender.

The key insight is that when we find a number larger than our current maximum, it triggers a cascade effect:

• The current 1st place moves to 2nd place
• The current 2nd place moves to 3rd place
• The current 3rd place gets knocked off the podium
• The new number takes 1st place

Similarly, if a number is between the 1st and 2nd maximum, it only affects positions 2 and 3. This cascading update pattern naturally maintains the correct order.

We initialize all three variables to negative infinity (-inf) as a sentinel value. This serves two purposes:

1. Any actual number in the array will be greater than -inf, ensuring proper updates
2. At the end, if m3 is still -inf, we know we never found three distinct numbers

The duplicate check if num in [m1, m2, m3] ensures we only consider distinct values, as the problem requires distinct maximums, not just the three largest occurrences.

This approach gives us O(n) time complexity with just a single pass through the array, and O(1) space complexity since we only use three variables regardless of input size.

Solution Approach

We implement a single-pass algorithm using three variables to track the top three distinct maximums.

Initialization: Set three variables m1, m2, and m3 to negative infinity (-inf). These represent the first, second, and third largest numbers respectively. Using -inf ensures any actual number in the array will be greater than our initial values.

Main Loop: For each number num in the array:

1. Skip duplicates: Check if num equals any of m1, m2, or m3. If it does, skip to the next iteration using continue. This ensures we only track distinct values.

2. Update maximums based on comparison:

   • If num > m1: This number is our new maximum. Perform cascading updates:

     m3, m2, m1 = m2, m1, num

     The old first maximum becomes the second, old second becomes third, and num becomes the new first.

   • Else if num > m2: This number fits between first and second. Update:

     m3, m2 = m2, num

     The old second maximum becomes third, and num becomes the new second.

   • Else if num > m3: This number only beats the third maximum:

     m3 = num

     Simply update m3 to this number.

Return Logic: After processing all numbers:

• If m3 != -inf: We found at least three distinct numbers, return m3
• Otherwise: Less than three distinct numbers exist, return m1 (the maximum)

The algorithm maintains the invariant that m1 >= m2 >= m3 for all non-infinity values, and each variable holds a distinct value. The time complexity is O(n) with a single pass, and space complexity is O(1) using only three variables.

Example Walkthrough

Let's walk through the solution with nums = [2, 2, 3, 1]:

Initial State:

• m1 = -inf, m2 = -inf, m3 = -inf

Processing num = 2:

• Check duplicates: 2 not in [-inf, -inf, -inf] ✓
• Compare: 2 > -inf (m1)
• Cascade update: m3 = m2 = -inf, m2 = m1 = -inf, m1 = 2
• New state: m1 = 2, m2 = -inf, m3 = -inf

Processing num = 2 (duplicate):

• Check duplicates: 2 is in [2, -inf, -inf]
• Skip this iteration (continue)
• State unchanged: m1 = 2, m2 = -inf, m3 = -inf

Processing num = 3:

• Check duplicates: 3 not in [2, -inf, -inf] ✓
• Compare: 3 > 2 (m1)
• Cascade update: m3 = m2 = -inf, m2 = m1 = 2, m1 = 3
• New state: m1 = 3, m2 = 2, m3 = -inf

Processing num = 1:

• Check duplicates: 1 not in [3, 2, -inf] ✓
• Compare: 1 < 3 (m1), so check next condition
• Compare: 1 < 2 (m2), so check next condition
• Compare: 1 > -inf (m3)
• Update: m3 = 1
• Final state: m1 = 3, m2 = 2, m3 = 1

Return Logic:

• Since m3 = 1 ≠ -inf, we found three distinct numbers
• Return m3 = 1

The algorithm correctly identifies the three distinct values (3, 2, 1) and returns the third maximum, which is 1.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array nums. The algorithm iterates through the array exactly once, and for each element, it performs a constant number of operations - checking if the number exists in the three tracked values and comparing/updating at most three variables.

The space complexity is O(1). The algorithm only uses three variables (m1, m2, m3) to track the three maximum values regardless of the input size. No additional data structures are created that scale with the input size.

Common Pitfalls

1. Incorrect Duplicate Check Using in Operator with Floats

The most significant pitfall in this solution is using the in operator to check if num exists in a list containing float('-inf'):

if num in [first_max, second_max, third_max]:
    continue

Why it's problematic:

• When the variables are still -inf, this creates a list like [float('-inf'), float('-inf'), float('-inf')]
• The in operator performs equality checks, which can be unreliable with floating-point infinity values
• This approach also creates a new list on every iteration, adding unnecessary overhead

Solution: Use explicit comparisons instead:

# Check for duplicates explicitly
if num == first_max or num == second_max or num == third_max:
    continue

2. Integer Overflow Concerns in Other Languages

While Python handles arbitrarily large integers, translating this solution to languages like Java or C++ requires careful consideration:

Problem: Using Integer.MIN_VALUE as initial values won't work if the array contains Integer.MIN_VALUE itself.

Solution for other languages: Use null values or a separate boolean flag:

# Alternative approach using None
first_max = second_max = third_max = None

for num in nums:
    # Skip duplicates
    if first_max == num or second_max == num or third_max == num:
        continue
  
    if first_max is None or num > first_max:
        third_max, second_max, first_max = second_max, first_max, num
    elif second_max is None or num > second_max:
        third_max, second_max = second_max, num
    elif third_max is None or num > third_max:
        third_max = num

return third_max if third_max is not None else first_max

3. Edge Case: Array Contains -inf

If the input array could theoretically contain float('-inf') as a valid element, the current solution would incorrectly handle it.

Solution: Use a different sentinel value or track count of distinct values:

def thirdMax(self, nums: List[int]) -> int:
    # Use a set to get distinct values first
    distinct = set(nums)
  
    if len(distinct) < 3:
        return max(distinct)
  
    # Remove max twice to get third max
    distinct.remove(max(distinct))
    distinct.remove(max(distinct))
    return max(distinct)

This approach is cleaner but uses O(n) space instead of O(1).