Third Maximum Number

Given an array nums, return the third largest (distinct) value.

Note: If the third largest number does not exist, return the largest value.

Example(s)

Example 1:

Input: nums = [1, 4, 2, 3, 5]
Output: 3
Explanation:
Distinct values: [1, 2, 3, 4, 5]
Sorted descending: [5, 4, 3, 2, 1]
Third largest: 3

Example 2:

Input: nums = [2, 3, 3, 5]
Output: 2
Explanation:
Distinct values: [2, 3, 5]
Sorted descending: [5, 3, 2]
Third largest: 2

Example 3:

Input: nums = [9, 5]
Output: 9
Explanation:
Distinct values: [5, 9]
Only 2 distinct values, so third largest doesn't exist.
Return the largest value: 9

Example 4:

Input: nums = [2, 2, 3, 1]
Output: 1
Explanation:
Distinct values: [1, 2, 3]
Sorted descending: [3, 2, 1]
Third largest: 1

Solution

The solution can use multiple approaches:

1. Sorting approach: Remove duplicates, sort, return third largest
2. Three variables: Track top 3 distinct values in one pass
3. Set + sort: Use set to get distinct values, then sort

JavaScript Solution

JavaScript Solution - Sorting

/**
* Find third largest distinct value
* @param {number[]} nums - Array of integers
* @return {number} - Third largest distinct value, or largest if doesn't exist
*/
function thirdMax(nums) {
// Get distinct values and sort in descending order
const distinct = Array.from(new Set(nums)).sort((a, b) => b - a);

// If we have at least 3 distinct values, return the third
if (distinct.length >= 3) {
  return distinct[2];
}

// Otherwise, return the largest (first element)
return distinct[0];
}

// Test cases
console.log('Example 1:', thirdMax([1, 4, 2, 3, 5])); // 3
console.log('Example 2:', thirdMax([2, 3, 3, 5])); // 2
console.log('Example 3:', thirdMax([9, 5])); // 9
console.log('Example 4:', thirdMax([2, 2, 3, 1])); // 1
console.log('Test 5:', thirdMax([3, 2, 1])); // 1
console.log('Test 6:', thirdMax([1, 1, 2])); // 1

Output:

Click "Run Code" to execute the code and see the results.

Python Solution

Python Solution - Sorting

from typing import List

def third_max(nums: List[int]) -> int:
  """
  Find third largest distinct value
  
  Args:
      nums: List of integers
      
  Returns:
      int: Third largest distinct value, or largest if doesn't exist
  """
  # Get distinct values and sort in descending order
  distinct = sorted(set(nums), reverse=True)
  
  # If we have at least 3 distinct values, return the third
  if len(distinct) >= 3:
      return distinct[2]
  
  # Otherwise, return the largest (first element)
  return distinct[0]

# Test cases
print('Example 1:', third_max([1, 4, 2, 3, 5]))  # 3
print('Example 2:', third_max([2, 3, 3, 5]))  # 2
print('Example 3:', third_max([9, 5]))  # 9
print('Example 4:', third_max([2, 2, 3, 1]))  # 1
print('Test 5:', third_max([3, 2, 1]))  # 1
print('Test 6:', third_max([1, 1, 2]))  # 1

Loading Python runtime...

Output:

Click "Run Code" to execute the code and see the results.

Alternative Solution (One Pass - Three Variables)

Here's an optimized solution that finds the top 3 in a single pass:

JavaScript One Pass

/**
 * One-pass solution using three variables
 */
function thirdMaxOptimized(nums) {
  let first = -Infinity;
  let second = -Infinity;
  let third = -Infinity;
  
  for (const num of nums) {
    // Skip if we've seen this value before (for distinct values)
    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;
    }
  }
  
  // If third largest doesn't exist, return largest
  return third === -Infinity ? first : third;
}

Python One Pass

def third_max_optimized(nums: List[int]) -> int:
    """
    One-pass solution using three variables
    """
    first = second = third = float('-inf')
    
    for num in nums:
        # Skip if we've seen this value before (for distinct values)
        if num == first or num == second or num == third:
            continue
        
        if num > first:
            third = second
            second = first
            first = num
        elif num > second:
            third = second
            second = num
        elif num > third:
            third = num
    
    # If third largest doesn't exist, return largest
    return first if third == float('-inf') else third

Alternative: Using Set with Manual Tracking

Here's another approach that explicitly tracks distinct values:

JavaScript Set Tracking

/**
 * Using set to track distinct values seen
 */
function thirdMaxSet(nums) {
  const seen = new Set();
  let first = -Infinity;
  let second = -Infinity;
  let third = -Infinity;
  
  for (const num of nums) {
    if (seen.has(num)) {
      continue; // Skip duplicates
    }
    
    seen.add(num);
    
    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 === -Infinity ? first : third;
}

Python Set Tracking

def third_max_set(nums: List[int]) -> int:
    """
    Using set to track distinct values seen
    """
    seen = set()
    first = second = third = float('-inf')
    
    for num in nums:
        if num in seen:
            continue  # Skip duplicates
        
        seen.add(num)
        
        if num > first:
            third = second
            second = first
            first = num
        elif num > second:
            third = second
            second = num
        elif num > third:
            third = num
    
    return first if third == float('-inf') else third

Complexity

• Time Complexity:
  • Sorting approach: O(n log n) - Sorting the distinct values
  • One-pass approach: O(n) - Single pass through the array
• Space Complexity:
  • Sorting approach: O(n) - For the distinct array
  • One-pass approach: O(1) - Only uses three variables

Approach

The solution uses sorting with distinct values:

1. Get distinct values: Remove duplicates using a Set
2. Sort descending: Sort distinct values in descending order
3. Check length:
   • If we have at least 3 distinct values, return the third (index 2)
   • Otherwise, return the largest (index 0)

Key Insights

• Distinct values: Only count each value once
• Sorting: Simplest approach, easy to understand
• One-pass optimization: Can find top 3 in O(n) time
• Fallback: If third doesn't exist, return largest
• Edge cases: Handle arrays with fewer than 3 distinct values

Step-by-Step Example

Let's trace through Example 1: nums = [1, 4, 2, 3, 5]

Step 1: Get distinct values
  Set: {1, 4, 2, 3, 5}
  Array: [1, 4, 2, 3, 5]

Step 2: Sort in descending order
  Sorted: [5, 4, 3, 2, 1]

Step 3: Check length
  distinct.length = 5 >= 3 ✓

Step 4: Return third largest
  distinct[2] = 3

Result: 3

Let's trace through Example 2: nums = [2, 3, 3, 5]

Step 1: Get distinct values
  Set: {2, 3, 5}
  Array: [2, 3, 5]

Step 2: Sort in descending order
  Sorted: [5, 3, 2]

Step 3: Check length
  distinct.length = 3 >= 3 ✓

Step 4: Return third largest
  distinct[2] = 2

Result: 2

Let's trace through Example 3: nums = [9, 5]

Step 1: Get distinct values
  Set: {9, 5}
  Array: [9, 5]

Step 2: Sort in descending order
  Sorted: [9, 5]

Step 3: Check length
  distinct.length = 2 < 3 ✗

Step 4: Return largest (fallback)
  distinct[0] = 9

Result: 9

Visual Representation

Example 1: nums = [1, 4, 2, 3, 5]
Distinct: [1, 2, 3, 4, 5]
Sorted:   [5, 4, 3, 2, 1]
          ↑  ↑  ↑
        1st 2nd 3rd → Return 3

Example 2: nums = [2, 3, 3, 5]
Distinct: [2, 3, 5]
Sorted:   [5, 3, 2]
          ↑  ↑  ↑
        1st 2nd 3rd → Return 2

Example 3: nums = [9, 5]
Distinct: [5, 9]
Sorted:   [9, 5]
          ↑
        1st (only) → Return 9

Edge Cases

• Less than 3 distinct values: Return the largest
• Exactly 3 distinct values: Return the third
• All same value: Return that value (only 1 distinct)
• Negative numbers: Works correctly
• Large array: Sorting approach handles it, one-pass is more efficient

Important Notes

• Distinct values: Duplicates don't count separately
• Third largest: Means the third largest distinct value
• Fallback rule: If third doesn't exist, return largest
• Sorting: O(n log n) but simple and clear
• One-pass: O(n) but more complex logic

Comparison of Approaches

Approach	Time	Space	Notes
Sorting	O(n log n)	O(n)	Simple, easy to understand
One-pass	O(n)	O(1)	More efficient, but more complex

Related Problems

• Kth Largest Element: Generalize to kth largest
• Top K Frequent Elements: Different problem
• Find Peak Element: Different problem
• Maximum Product of Three Numbers: Uses similar top-3 tracking

Takeaways

• Sorting approach is simple and intuitive
• One-pass optimization is more efficient for large arrays
• Distinct values requirement means duplicates don't count
• Fallback rule handles edge cases gracefully
• O(n log n) vs O(n) trade-off between simplicity and efficiency