Third Maximum Number — LeetCode 414 Python Solution

The problem

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

Input

nums = [3,2,1]

Output

1

Explanation

The first distinct maximum is 3.

Python solution

class Solution:
    def thirdMax(self, nums: List[int]) -> int:
        m1 = m2 = m3 = -inf
        for num in nums:
            if num in [m1, m2, m3]:
                continue
            if num > m1:
                m3, m2, m1 = m2, m1, num
            elif num > m2:
                m3, m2 = m2, num
            elif num > m3:
                m3 = num
        return m3 if m3 != -inf else m1

Complexity

Pattern: Sorting

Spend O(n log n) once to buy an ordering that makes the rest of the problem trivial. LeetCode 414. Third Maximum Number is filed here because LeetCode tags it Sorting, which is the vocabulary this hub collects.

The sorting guide has the Python template for the pattern and the 401 LeetCode problems that use it.

Related problems