Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

414. Third Maximum Number

Time: $O(n)$

Space: $O(1)$

			


class Solution {
 public:
  int thirdMax(vector<int>& 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;
  }
};




			


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;
  }
}




			


class Solution {
 public:
  int thirdMax(vector<int>& nums) {
    priority_queue<int, vector<int>, greater<>> minHeap;
    unordered_set<int> 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();
  }
};