Vultr DocsLatest Content

Third Maximum Number

Updated on 30 June, 2025
Third Maximum Number header image

Problem Statement

Imagine you are given an array of integers called nums. Your task is to find the third highest unique number in that array. It's crucial to note that the number has to be distinctly the third highest; duplicates do not count multiple times toward this ranking. If the array does not have enough unique elements to have a third distinct maximum, then you should return the highest value from the array. This problem involves understanding array operations, particularly sorting and handling unique values.

Examples

Example 1

Input:

nums = [3,2,1]

Output:

1

Explanation:

The first distinct maximum is 3.
The second distinct maximum is 2.
The third distinct maximum is 1.

Example 2

Input:

nums = [1,2]

Output:

2

Explanation:

The first distinct maximum is 2.
The second distinct maximum is 1.
The third distinct maximum does not exist, so the maximum (2) is returned instead.

Example 3

Input:

nums = [2,2,3,1]

Output:

1

Explanation:

The first distinct maximum is 3.
The second distinct maximum is 2 (both 2's are counted together since they have the same value).
The third distinct maximum is 1.

Constraints

  • 1 <= nums.length <= 104
  • -231 <= nums[i] <= 231 - 1

Approach and Intuition

Our goal is to identify the third distinct maximum number in the list provided, or fallback to the overall maximum if fewer than three unique numbers are present.

  1. Start by sorting the array in descending order to get the numbers arranged from the highest to the lowest.

  2. Iterate through the sorted list while keeping track of the current ranking of distinct maximums we encounter. This can be achieved by comparing the current element with the previous one (if any) to see if they are different - if they are, we count it as a new distinct maximum.

  3. We need to keep a counter for how many distinct maximums we've passed. Once this counter reaches three, we can immediately return the current element as it is the third distinct maximum.

  4. If we complete our iteration without finding three distinct maximums, it means our array contains fewer than three different numbers and as a fallback, we can return the very first element of our sorted array (which is the overall maximum).

Let's elaborate this with the examples from the problem:

  • For the array [3, 2, 1], sorting it gives [3, 2, 1] directly showing the three distinct maximums easily recognized.

  • On the other hand, the array [1, 2] only after sorting results in [2, 1] with just two distinct numbers where the greatest number has to be returned due to lacking a third.

  • In the case of [2, 2, 3, 1], sorting changes it to [3, 2, 2, 1], counting distinct values gives us three distinct maximums as 3 (first maximum), 2 (second maximum, skipping the duplicate), and 1 (third maximum).

This discussion shows that the main challenges include sorting the array, maintaining a count of distinct maxima, and handling arrays that do not have three distinct numbers efficiently.

Solutions

  • C++
  • Java
  • JavaScript
  • Python
cpp 
class Solution {
public:
    int thirdMaximum(vector<int>& nums) {
        pair<int, bool> max1 = {-1, false};
        pair<int, bool> max2 = {-1, false};
        pair<int, bool> max3 = {-1, false};
            
        for (int& value : nums) {
            if ((max1.second && max1.first == value) || 
                (max2.second && max2.first == value) || 
                (max3.second && max3.first == value)) {
                continue;
            }
                
            if (!max1.second || max1.first <= value) {
                max3 = max2;
                max2 = max1;
                max1 = make_pair(value, true);
            } else if (!max2.second || max2.first <= value) {
                max3 = max2;
                max2 = make_pair(value, true);
            } else if (!max3.second || max3.first <= value) {
                max3 = make_pair(value, true);
            }
        }
            
        if (!max3.second) {
            return max1.first;
        }
            
        return max3.first;
    }
};

The provided C++ solution identifies the third maximum number in a vector of integers, nums. If there are fewer than three unique numbers, the solution returns the highest number.

  • Initialize three pairs (max1, max2, max3) to store the top three unique values and corresponding flags indicating whether these values have been updated.
  • Iterate through each element in nums:
    • Skip the iteration if the number matches any of the top three values stored.
    • Evaluate and update max1, max2, and max3 based on the current number's value relative to these stored maximums.
    • Ensure values only update if they are unique and qualify as a new top three value, shifting other values down as necessary.
  • Use the second value of each pair to determine if a valid third maximum exists.
  • Return the third maximum if it exists; otherwise, return the highest value available.

This method efficiently tracks the top three distinct values in a single pass through the array, updating conditional logic to maintain or shift these values as needed based on comparisons. This approach avoids sorting or additional data structures, maintaining linear time complexity relative to the number of input elements.

java 
class Solution {
    public int findThirdMaximum(int[] values) {
        Pair<Integer, Boolean> highest = new Pair<Integer, Boolean>(-1, false);
        Pair<Integer, Boolean> secondHighest = new Pair<Integer, Boolean>(-1, false);
        Pair<Integer, Boolean> thirdHighest = new Pair<Integer, Boolean>(-1, false);
    
        for (int value : values) {
            if ((highest.getValue() && highest.getKey() == value) || 
                (secondHighest.getValue() && secondHighest.getKey() == value) || 
                (thirdHighest.getValue() && thirdHighest.getKey() == value)) {
                continue;
            }
    
            if (!highest.getValue() || highest.getKey() <= value) {
                thirdHighest = secondHighest;
                secondHighest = highest;
                highest = new Pair<Integer, Boolean>(value, true);
            }
            else if (!secondHighest.getValue() || secondHighest.getKey() <= value) {
                thirdHighest = secondHighest;
                secondHighest = new Pair<Integer, Boolean>(value, true);
            }
            else if (!thirdHighest.getValue() || thirdHighest.getKey() <= value) {
                thirdHighest = new Pair<Integer, Boolean>(value, true);
            }
        }
    
        if (!thirdHighest.getValue()) {
            return highest.getKey();
        }
    
        return thirdHighest.getKey();
    }
}

The given Java solution is designed to find the third maximum number in an array of integers. If the third maximum does not exist because all numbers are the same or there are less than three unique numbers, the maximum number is returned instead. This method employs an efficient selection approach using three variables: highest, secondHighest, and thirdHighest, to keep track of the top three unique values during a single pass through the array.

  • The function findThirdMaximum accepts an array of integers values.
  • It uses three Pair<Integer, Boolean> objects to keep track of the values and their validation status:
    • highest corresponds to the maximum number found.
    • secondHighest stores the second highest number.
    • thirdHighest represents the third highest number.
  • The method iterates through each value in the input array:
    1. It first checks if the current value is the same as any of the recorded top three values. If it is, it skips to the next value.
    2. If the value is greater than or equal to highest, it shifts the current highest and secondHighest down the chain and sets the new highest.
    3. If the value does not exceed highest but is higher than or equal to secondHighest, secondHighest and thirdHighest are updated accordingly.
    4. If the value falls under neither of the above conditions but is still higher than or equal to thirdHighest, then thirdHighest is updated.
  • After iterating through all elements, the method checks if a valid thirdHighest value exists. If not, it returns highest.

This solution effectively tracks and updates the top three unique values in a single scan of the input array, ensuring an O(n) time complexity where n is the number of elements in the array. It handles edge cases where there are fewer than three unique values gracefully by returning the maximum available value.

js 
let findThirdMax = function(array) {
    let maxOne = [-1, false];
    let maxTwo = [-1, false];
    let maxThree = [-1, false];
    
    for (let i in array) {
        let value = array[i];
            
        // Skip if current value is already considered
        if ((maxOne[1] && maxOne[0] == value) || 
            (maxTwo[1] && maxTwo[0] == value) || 
            (maxThree[1] && maxThree[0] == value)) {
            continue;
        }
    
        // Update the maximum values based on current value's ranking
        if (!maxOne[1] || maxOne[0] <= value) {
            maxThree = maxTwo;
            maxTwo = maxOne;
            maxOne = [value, true];
        } else if (!maxTwo[1] || maxTwo[0] <= value) {
            maxThree = maxTwo;
            maxTwo = [value, true];
        } else if (!maxThree[1] || maxThree[0] <= value) {
            maxThree = [value, true];
        }
    }
    
    // Return first max if third max is unavailable
    if (!maxThree[1]) {
        return maxOne[0];
    }
    
    return maxThree[0];
};

The JavaScript function findThirdMax you provided aims to find the third distinct maximum number in an array. If fewer than three unique maximums exist, it returns the highest number. Here's an explanation of how the function works:

  • First, it initializes three variables (maxOne, maxTwo, maxThree) to track the top three distinct values. Each variable is an array where the first element is the value and the second element is a Boolean indicating if the position has been set.

  • The function iterates over each element of the input array. For each element:

    • It checks if the current value is already one of the identified maximums. If so, it skips further checks for that element.
    • It then checks and updates the maximum values by comparing the current element against maxOne, maxTwo, and maxThree. This involves shifting the values down if a new top three value is found (e.g., if a new maximum is found, then the previous first and second maximums are moved to second and third place respectively).

  • After iterating through all elements:

    • If the third maximum doesn't have a set value (indicating less than three unique values were found), the function returns the maximum value found (maxOne[0]).
    • Otherwise, it returns the third maximum value.

This approach assures that the function dynamically adjusts the top values as it progresses through the array, efficiently identifying the third distinct maximum value. The overall complexity is linear, making it suitable for large arrays.

python 
class Solution:
    def findThirdMaximum(self, array: List[int]) -> int:
        top1 = (-1, False)
        top2 = (-1, False)
        top3 = (-1, False)
            
        for number in array:
            # Check if the number is already one of the maxima
            if (top1[1] and top1[0] == number) or \
               (top2[1] and top2[0] == number) or \
               (top3[1] and top3[0] == number):
                continue
                
            # Update top1, top2, and top3 accordingly
            if not top1[1] or top1[0] <= number:
                top3 = top2
                top2 = top1
                top1 = (number, True)
            elif not top2[1] or top2[0] <= number:
                top3 = top2
                top2 = (number, True)
            elif not top3[1] or top3[0] <= number:
                top3 = (number, True)
            
        # Return the third maximum if it exists
        if not top3[1]:
            return top1[0]
            
        return top3[0]

The provided Python code defines a solution for finding the third maximum number in a list of integers. If the list does not have a third distinct maximum, the code returns the largest value. The implementation is efficient and avoids sorting the entire list, which makes it potentially faster for large lists.

Here's how the code works:

  • It initializes three tuples: top1, top2, and top3, to track the first, second, and third maximums. Each tuple contains the value and a Boolean indicating if it has been updated.
  • The code iterates through each number in the input list:
    • It first checks if the current number is already recorded as one of the top three numbers. If yes, it skips to the next number.
    • It then updates the top values based on conditions. If the current number is greater than top1, the values shift: top1 moves to top2, and top2 to top3, and the current number becomes the new top1.
    • Similar logic applies for updating top2 and top3.
  • After the loop, the code checks the Boolean of top3. If top3 has not been updated (i.e., there were less than three distinct numbers), it returns top1[0]; otherwise, it returns top3[0].

This method allows finding the third maximum number or an alternative without needing to sort or use additional data structures like heaps or sets, providing a direct approach to the solution with constant space complexity.

Comments

No comments yet.