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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Third Maximum Number

Difficulty: Easy

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

Key Insights

  • The problem requires finding distinct maximums, meaning duplicate values should not be counted more than once.
  • If there are fewer than three distinct values, we should return the maximum value.
  • The input can be as large as 10,000 elements, so an efficient solution is desired.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve the problem, we can maintain three variables to track the first, second, and third distinct maximums as we iterate through the array. We will use a set to avoid counting duplicates. If we find a new distinct maximum, we update our variables accordingly. If we finish iterating and do not have a third distinct maximum, we return the maximum found.

Code Solutions

def thirdMax(nums):
    first = second = third = float('-inf')
    distinct_count = 0

    for num in nums:
        if num > first:
            first, second, third = num, first, second
            distinct_count += 1
        elif first > num > second:
            second, third = num, second
            distinct_count += 1
        elif second > num > third:
            third = num
            distinct_count += 1

    return third if distinct_count == 3 else first
← Back to All Questions