# 414. Third Maximum Number

## Approach 1: $O(n)$

• Time: $O(n)$
• Space: $O(1)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution { public: int thirdMax(vector& nums) { long max1 = LONG_MIN; // The maximum long max2 = LONG_MIN; // 2nd maximum long max3 = LONG_MIN; // 3rd maximum for (const int num : nums) if (num > max1) { max3 = max2; max2 = max1; max1 = num; } else if (max1 > num && num > max2) { max3 = max2; max2 = num; } else if (max2 > num && num > max3) { max3 = num; } return max3 == LONG_MIN ? max1 : max3; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 public class Solution { public int thirdMax(int[] nums) { long max1 = Long.MIN_VALUE; // The maximum long max2 = Long.MIN_VALUE; // 2nd maximum long max3 = Long.MIN_VALUE; // 3rd maximum for (final int num : nums) if (num > max1) { max3 = max2; max2 = max1; max1 = num; } else if (max1 > num && num > max2) { max3 = max2; max2 = num; } else if (max2 > num && num > max3) { max3 = num; } return max3 == Long.MIN_VALUE ? (int) max1 : (int) max3; } } 

## Approach 2: Heap

• Time: $O(n\log 3) = O(n)$
• Space: $O(\log 3) = O(1)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution { public: int thirdMax(vector& nums) { priority_queue, greater<>> minHeap; unordered_set seen; for (const int num : nums) if (!seen.count(num)) { seen.insert(num); minHeap.push(num); if (minHeap.size() > 3) minHeap.pop(); } if (minHeap.size() == 2) minHeap.pop(); return minHeap.top(); } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 public class Solution { public int thirdMax(int[] nums) { Queue minHeap = new PriorityQueue<>(); Set seen = new HashSet<>(); for (final int num : nums) if (seen.add(num)) { minHeap.offer(num); if (minHeap.size() > 3) minHeap.poll(); } if (minHeap.size() == 2) minHeap.poll(); return minHeap.peek(); } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution: def thirdMax(self, nums: List[int]) -> int: minHeap = [] seen = set() for num in nums: if num not in seen: seen.add(num) heapq.heappush(minHeap, num) if len(minHeap) > 3: heapq.heappop(minHeap) if len(minHeap) == 2: heapq.heappop(minHeap) return minHeap[0]