Problem statement

https://leetcode.com/problems/third-maximum-number/

Solution

Just keep list of 3 elements and insert in proper place. Like we have 10, 6, 2 and we have >10 we insert before first element, if we have >6, we insert before second element, and we have >2 we insert before third element. Then we remove last element. Or we can use functionality of bisect.insort(), which will insert element in O(1), because size is always no more than 3.

Complexity

Time complexity is O(n), space is O(1).

Code

class Solution:
    def thirdMax(self, nums):
        cands = []
        for num in nums:
            if num not in cands: insort(cands, num)
            if len(cands) == 4: cands.pop(0)
        
        return cands[0] if len(cands) == 3 else cands[-1]