Skip to main content

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 - 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.

Alternative Solution (One Pass - Three Variables)​

Here's an optimized solution that finds the top 3 in a single 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;
}

Alternative: Using Set with Manual Tracking​

Here's another approach that explicitly tracks distinct values:

/**
 * 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;
}

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​

ApproachTimeSpaceNotes
SortingO(n log n)O(n)Simple, easy to understand
One-passO(n)O(1)More efficient, but more complex
  • 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