We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Third Maximum Number

Number: 414

Difficulty: Easy

Paid? No

Companies: Google, Amazon, Bloomberg, Goldman Sachs, TikTok, Microsoft, Adobe

Problem Description

Given an integer array nums, return the third distinct maximum number in this array. If the third maximum does not exist, return the maximum number.

Key Insights

  • We need to consider only distinct values in the array.
  • Use variables or a data structure to track the top 3 distinct maximum numbers.
  • We need an O(n) solution, so we should avoid unnecessary sorting.
  • Edge-case: If there are fewer than 3 distinct numbers, the maximum among them should be returned.

Space and Time Complexity

Time Complexity: O(n) because we iterate through the array once.
Space Complexity: O(1) since we only maintain a fixed number of variables.

Solution

We iterate through the nums array and maintain three variables to store the first, second, and third distinct maximum numbers. For each number in the array, we check whether it is already one of the three maximums (to handle duplicates). If not, we update the maximums accordingly:

  1. If the current number is greater than the first maximum, then update the first, second, and third maximums.
  2. Else if the current number is between the first maximum and the second, update the second and third maximums accordingly.
  3. Else if the current number is between the second maximum and the third, update the third maximum.

After processing all elements, if the third maximum is still unassigned (i.e., there are less than three distinct numbers), return the first maximum. This approach uses constant extra space and only one pass through the input array.

Code Solutions

# Define function thirdMax that returns the third distinct maximum number in the array.
def thirdMax(nums):
    # Initialize three maximum variables to None to represent their absence.
    first = second = third = None
    
    # Iterate over each number in the nums array.
    for num in nums:
        # Skip the current number if it is already one of the three maximums.
        if num == first or num == second or num == third:
            continue
        
        # Update the maximums based on the current number's value.
        if first is None or num > first:
            # Shift down the values: first becomes second, second becomes third.
            third, second, first = second, first, num
        elif second is None or num > second:
            # Update second and shift second to third.
            third, second = second, num
        elif third is None or num > third:
            # Update third maximum.
            third = num
    
    # If there is no third distinct maximum, return the first maximum.
    return first if third is None else third

# Example usage:
print(thirdMax([3,2,1]))  # Output: 1
print(thirdMax([1,2]))    # Output: 2
print(thirdMax([2,2,3,1]))  # Output: 1
← Back to All Questions