Skip to content

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<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;
  }
};
 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<int>& nums) {
    priority_queue<int, vector<int>, greater<>> pq;  // min-heap
    unordered_set<int> seen;

    for (const int num : nums)
      if (!seen.count(num)) {
        seen.insert(num);
        pq.push(num);
        if (pq.size() > 3)
          pq.pop();
      }

    if (pq.size() == 2)
      pq.pop();

    return pq.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<Integer> pq = new PriorityQueue<>(); // min-heap
    Set<Integer> seen = new HashSet<>();

    for (final int num : nums)
      if (seen.add(num)) {
        pq.offer(num);
        if (pq.size() > 3)
          pq.poll();
      }

    if (pq.size() == 2)
      pq.poll();

    return pq.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:
    pq = []
    seen = set()

    for num in nums:
      if num not in seen:
        seen.add(num)
        heapq.heappush(pq, num)
        if len(pq) > 3:
          heapq.heappop(pq)

    if len(pq) == 2:
      heapq.heappop(pq)

    return pq[0]
Back to top