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;  // the second maximum
    long max3 = LONG_MIN;  // the third 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
class Solution {
  public int thirdMax(int[] nums) {
    long max1 = Long.MIN_VALUE; // the maximum
    long max2 = Long.MIN_VALUE; // the second maximum
    long max3 = Long.MIN_VALUE; // the third 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;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
  def thirdMax(self, nums: list[int]) -> int:
    max1 = -math.inf  # the maximum
    max2 = -math.inf  # the second maximum
    max3 = -math.inf  # the third maximum

    for num in nums:
      if num > max1:
        max3 = max2
        max2 = max1
        max1 = num
      elif max1 > num and num > max2:
        max3 = max2
        max2 = num
      elif max2 > num and num > max3:
        max3 = num

    return max1 if max3 == -math.inf else 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<>> minHeap;
    unordered_set<int> seen;

    for (const int num : nums)
      if (!seen.contains(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
class Solution {
  public int thirdMax(int[] nums) {
    Queue<Integer> minHeap = new PriorityQueue<>();
    Set<Integer> 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]