414. Third Maximum Number

Problem Link

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.

 

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

 

Follow up: Can you find an O(n) solution?

Solution

---

Python3

class Solution:
    def thirdMax(self, nums: List[int]) -> int:
        if not nums: return 0
        
        first = second = third = float('-inf')
        
        for num in nums:
            if num > first:
                first, second, third = num, first, second
            
            elif num > second and num < first:
                second, third = num, second
            
            elif num > third and num < second:
                third = num
            
            print(first, second, third)
        
        return third if third != float('-inf') else first