Third Maximum Number

Difficulty: Easy | Acceptance: 39.30% | Paid: No Topics: Array, Sorting

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.

• Examples
• Constraints
• Sorting Approach
• Three Variables Approach
• Set + Heap Approach

Examples

Input: nums = [3,2,1]
Output: 1
Explanation: The third maximum is 1.

Input: nums = [1,2]
Output: 2
Explanation: The third maximum does not exist, so the maximum (2) is returned instead.

Input: nums = [2,2,3,1]
Output: 1
Explanation: Note that the third maximum here means the third maximum distinct number. Both numbers with value 2 are both considered as second maximum.

Constraints

- 1 <= nums.length <= 10^4
- -2^31 <= nums[i] <= 2^31 - 1

Sorting Approach

Intuition Convert the array to a set to remove duplicates, sort in descending order, and pick the third element if it exists.

Steps

• Create a set from the array to get distinct elements
• Sort the distinct elements in descending order
• Return the third element if there are at least 3 distinct elements, otherwise return the maximum

class Solution:
    def thirdMax(self, nums: List[int]) -> int:
        nums = sorted(set(nums), reverse=True)
        if len(nums) >= 3:
            return nums[2]
        return nums[0]

Complexity

• Time: O(n log n)
• Space: O(n)
• Notes: Simple and readable, but sorting is not necessary for this problem

Three Variables Approach

Intuition Maintain three variables to track the top three distinct maximums while iterating through the array once.

Steps

• Initialize three variables to track first, second, and third maximums
• Iterate through each number, skipping duplicates
• Update the three variables based on comparisons
• Return third maximum if it exists, otherwise return first maximum

class Solution:
    def thirdMax(self, nums: List[int]) -> int:
        first = second = third = None
        for num in nums:
            if num == first or num == second or num == third:
                continue
            if first is None or num > first:
                third = second
                second = first
                first = num
            elif second is None or num > second:
                third = second
                second = num
            elif third is None or num > third:
                third = num
        return third if third is not None else first

Complexity

• Time: O(n)
• Space: O(1)
• Notes: Optimal single-pass solution with constant space

Set + Heap Approach

Intuition Use a set to get distinct elements, then either use a heap or direct access to find the third maximum.

Steps

• Create a set from the array to remove duplicates
• If fewer than 3 distinct elements, return the maximum
• Otherwise, find the third largest element using heap or sorting

import heapq

class Solution:
    def thirdMax(self, nums: List[int]) -> int:
        distinct = set(nums)
        if len(distinct) < 3:
            return max(distinct)
        return heapq.nlargest(3, distinct)[-1]

Complexity

• Time: O(n) or O(n log n) depending on implementation
• Space: O(n)
• Notes: Clean approach using set operations, C++ set is already sorted