Domain 1EasyCORE

Third Maximum Number

The problem requires finding the third maximum number in an integer array `nums`. If the third maximum does not exist (i.e., there are fewer than three distinct numbers), we should return the maximum number. The input is a list of integers, and the output is a single integer. Key constraints include handling duplicates, negative numbers, and ensuring the solution has linear time complexity.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Array

414. Third Maximum Number

Model: qwen2.5-coder:14b
Topics: Array
FAANG asked: 1
Acceptance rate: 30.7%


Problem Breakdown

The problem requires finding the third maximum number in an integer array nums. If the third maximum does not exist (i.e., there are fewer than three distinct numbers), we should return the maximum number. The input is a list of integers, and the output is a single integer. Key constraints include handling duplicates, negative numbers, and ensuring the solution has linear time complexity.

Intuition

A brute-force approach would involve sorting the array and then selecting the third last element if it exists. However, this approach has a time complexity of O(n log n), which is not optimal for large arrays. The key insight is to maintain three variables to track the top three distinct maximum numbers as we iterate through the array once.

Approach

  1. Initialize three variables first, second, and third to negative infinity. These will store the first, second, and third maximum numbers respectively.
  2. Iterate through each number in the array:
    • If the current number is greater than first, update third to be second, second to be first, and first to be the current number.
    • Else if the current number is greater than second and not equal to first, update third to be second, and second to be the current number.
    • Else if the current number is greater than third and not equal to second or first, update third to be the current number.
  3. After iterating through the array, check if third is still negative infinity. If it is, return first; otherwise, return third.

Complexity Analysis

  • Time complexity: O(n), where n is the length of the input array. We iterate through the array once.
  • Space complexity: O(1), as we use a constant amount of extra space.

Solution

def thirdMax(nums):
    first = second = third = float('-inf')
    
    for num in nums:
        if num > first:
            third = second
            second = first
            first = num
        elif num > second and num != first:
            third = second
            second = num
        elif num > third and num != second and num != first:
            third = num
    
    return third if third != float('-inf') else first

Edge Cases Handled

  • Empty Array: The function initializes first, second, and third to negative infinity, so it will correctly return the maximum number in an empty array.
  • Duplicates: The conditionals ensure that duplicates do not affect the ranking of distinct numbers.
  • Negative Numbers: The use of negative infinity ensures that negative numbers are handled correctly without special cases.
  • Single Element Array: If the array has only one element, third remains negative infinity, and the function returns the single element as the maximum.