Given a non-empty array of integers, return the third maximum number in this array. If it does not exist, return the maximum number. The time complexity must be in O(n).

Example 1:

Input: [3, 2, 1]

Output: 1

Explanation: The third maximum is 1.



Example 2:

Input: [1, 2]

Output: 2

Explanation: The third maximum does not exist, so the maximum (2) is returned instead.



Example 3:

Input: [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.

Difficulty: introductory

Starter code:

class Solution:
    def thirdMax(self, nums: List[int]) -> int:
        

Solutions:
class Solution:
     def thirdMax(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         nums = sorted(list(set(nums)))
         if len(nums)<3:
             return max(nums)
         else:
             return nums[-3]
 
             


class Solution:
     def thirdMax(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         v = [float('-inf'), float('-inf'), float('-inf')]
         for num in nums:
             if num not in v:
                if num > v[0]:
                    v = [num, v[0], v[1]]
 
                elif num > v[1]:
                    v = [v[0], num, v[1]]
 
                elif num > v[2]:
                    v = [v[0], v[1], num]
 
         return max(nums) if float('-inf') in v else v[2]
 


class Solution:
     def thirdMax(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         max3 = [nums[0], None, None]
         for i in range(1, len(nums)):
             if nums[i] in max3: continue
             if nums[i] > max3[0]:
                 max3[2] = max3[1]
                 max3[1] = max3[0]
                 max3[0] = nums[i]
             elif max3[1] is None or nums[i] > max3[1]:
                 max3[2] = max3[1]
                 max3[1] = nums[i]
             elif max3[2] is None or nums[i] > max3[2]:
                 max3[2] = nums[i]
             else: continue
         if None in max3: return max3[0]
         else: return max3[2]
                 


class Solution:
     def thirdMax(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         n = len(nums)
         m3 = [nums[0]]
         for y in nums[1:]:
             if m3[0] != y:
                 if len(m3) == 1:
                     if m3[0] > y:
                         m3.append(y)
                     else:
                         m3.insert(0, y)
                 elif m3[1] != y:
                     if m3[0] < y:
                         m3.insert(0, y)
                     elif m3[1] < y:
                         m3.insert(1, y)
                     else:
                         m3.append(y)
                     break
 
         if len(m3) < 3:
             return max(m3)
 
         for y in nums[3:]:
             if y==m3[0] or y==m3[1] or y<=m3[2]:
                 continue
             m3.pop()
             if y > m3[0]:
                 m3.insert(0, y)
             elif y > m3[1]:
                 m3.insert(1, y)
             else:
                 m3.append(y)
         return m3[2]

class Solution:
     def thirdMax(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         max3, max2, max1 = float("inf"), float("inf"), float("inf")
         
         for num in nums:
             carry = num
             
             if max3 == carry or max2 == carry or max1 == carry: continue
             
             if max3 == float("inf"):
                 max3 = carry
                 continue
             else:
                 if max3 < carry:
                     max3, carry = carry, max3
                 # else:
                 #     continue
                     
             if max2 == float("inf"):
                 max2 = carry
                 continue
             else:
                 if max2 < carry:
                     max2, carry = carry, max2
                 # else:
                 #     continue
             
             if max1 == float("inf"):
                 max1 = carry
                 continue
             else:
                 if max1 < carry:
                     max1 = carry
             
         print((max3, max2, max1))
         
         return max1 if max1 != float("inf") else max3
             
             


class Solution:
     def thirdMax(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         if len(nums) < 3:
             return max(nums)
         m1 = m2 = m3 = -2 ** 32
         for v in nums:
             if v == m1 or v == m2 or v == m3:
                 continue
             if v > m1:
                 m1, m2, m3 = v, m1, m2
             elif v == m1 or v > m2:
                 m2, m3 = v, m2
             elif v == m2 or v > m3:
                 m3 = v
         return m3 if m3 > -2 ** 32 else max(nums)

class Solution:
     def thirdMax(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         max3 = [nums[0], None, None]
         for i in range(1, len(nums)):
             if nums[i] in max3: continue
             if nums[i] > max3[0]:
                 max3 = [nums[i], max3[0],max3[1]]
             elif max3[1] is None or nums[i] > max3[1]:
                 max3 = [ max3[0],nums[i],max3[1]]
             elif max3[2] is None or nums[i] > max3[2]:
                 max3 = [ max3[0],max3[1], nums[i]]
             else: continue
         if None in max3: return max3[0]
         else: return max3[2]
                 


class Solution:
     def thirdMax(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         if not nums:
             return None
         
         seen = set([])
         import heapq
         
         min_heap = []
         max_number = nums[0]
         
         for num in nums:
             if num not in seen:
                 max_number = max(max_number, num)
                 seen.add(num)
                 if len(min_heap) == 3:
                     if min_heap[0] < num:
                         heapq.heappop(min_heap)
                     else:
                         continue
                 heapq.heappush(min_heap, num)
                     
 
         if len(min_heap) < 3:
             return max_number
         
         return heapq.heappop(min_heap)

class Solution:
     def thirdMax(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         
         """
         if len(nums) == 2 or len(nums) == 1:
             return max(nums)
         
         maxes = [nums[0], nums[1], nums[2]]
         maxes.sort() # ascending
         
         for i in range(3, len(nums)):
             pos = self.findPos(nums[i], maxes)
             if pos != None:
                 maxes[pos] = nums[i]
                 
         if maxes[0] == maxes[1] or maxes[1] == maxes[2]:
             return maxes[2]
         else:
             return maxes[0]
                 
     
     def findPos(self, val, maxes):
         maxPos = None
         for ind, aMax in enumerate(maxes):
             if val > aMax:
                 maxPos = ind
             
         return maxPos
         """
         
         maxes = []
         
         for i in nums:
             if self.isNew(i, maxes):
                 if len(maxes) < 3:
                     maxes.append(i)
                     maxes.sort() # ascending
                 else:
                     pos = self.findPos(i, maxes)
                     if pos != None:
                         maxes[pos] = i
                         maxes.sort()
         
         if len(maxes) == 3:
             return maxes[0]
         else:
             return maxes[-1]
                 
     
     def isNew(self, val, maxes):
         isNew = True
         for i in maxes:
             if val == i:
                 isNew = False
         return isNew
     
     def findPos(self, val, maxes):
         for ind, aMax in enumerate(maxes):
             if val > aMax:
                 return ind
             
         return None

class Solution:
     def thirdMax(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         stack = [float('-inf'), float('-inf'), float('-inf')]
         
         for num in nums:
             if num > stack[0]:
                 stack = [num, stack[0], stack[1]]
             elif num < stack[0]:
                 if num > stack[1]:
                     stack = [stack[0], num, stack[1]]
                 elif num < stack[1]:
                     if num > stack[2]:
                         stack = [stack[0], stack[1], num]
         
         if stack[-1] == float('-inf'):
             return stack[0]
         return stack[-1]

class Solution:
     def thirdMax(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         max_list = [None]*3
         max_list[0] = nums[0]
         for num in nums[1:]:
             print(max_list)
             if num > max_list[0]:
                 max_list[2] = max_list[1]
                 max_list[1] = max_list[0]
                 max_list[0] = num
             if max_list[1]:
                 if max_list[0] > num > max_list[1]:
                     max_list[2] = max_list[1]
                     max_list[1] = num
                 if max_list[2]:
                     if max_list[1] > num > max_list[2]:
                         max_list[2] = num   
                 elif max_list[1] > num:
                     max_list[2] = num
             elif max_list[0] > num:
                 max_list[1] = num
         return max_list[2] if max_list[2] is not None else max_list[0]

class Solution:
     def thirdMax(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         R = []
 
         for n in nums:
             if n not in R:
                 if len(R) < 3:
                     R.append(n)
                 elif min(R) < n:
                     R.remove(min(R))
                     R.append(n)
                 R = sorted(R)
         return R[0] if len(R) == 3 else max(R)


class Solution:
     def thirdMax(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         if not nums:
             return None
         nums = set(nums)
         if len(nums)<3:
             return max(nums)
         max3 = [-float('inf'),-float('inf'),-float('inf')]
         for n in nums:
             if n > max3[0]:
                 max3[0],max3[1],max3[2] = n,max3[0],max3[1]
             elif n > max3[1]:
                 max3[1],max3[2] = n, max3[1]
             elif n > max3[2]:
                 max3[2] = n
         return max3[2]


class Solution:
     def thirdMax(self, nums):
         a = b = c = -9999999999
         for n in nums:
             if n > c and n != b and n != a:
                 c = n
                 if c > b:
                     b,c = c,b
                 if b > a:
                     a,b = b,a
         if c == -9999999999:
             return a
         return c