Third Maximum Number Solution in C++

Problem Description

Ah, the classic “Third Maximum Number” problem! It’s like trying to find the third-best friend in a group of two. You know, the one who always gets left out of the selfies? The task is simple: given an array of integers, you need to find the third distinct maximum number. If it doesn’t exist, just return the maximum number. It’s like being told to find the third slice of pizza when there are only two left—good luck with that!

Imagine you’re at a party, and everyone is bragging about their achievements. You have the guy who just got a promotion (maximum), the one who finally learned to cook (second maximum), and then there’s you, who just managed to microwave a frozen dinner (third maximum). If you’re not careful, you might just end up with the same old stories!

Code Solution

Copy Code

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

Approach

The approach here is straightforward yet clever. We maintain three variables to track the first, second, and third maximum numbers. As we iterate through the array, we update these variables based on the current number. If the number is greater than the first maximum, we shift the values down the line. If it fits between the first and second, it becomes the second maximum, and so on. It’s like a game of musical chairs, but with numbers!

Time and Space Complexity

Time Complexity: O(n), where n is the number of elements in the array. We only traverse the array once.

Space Complexity: O(1), as we are using a constant amount of space for our three maximum variables.

Real-World Example

Let’s say you’re at a talent show. The first contestant sings like a superstar (maximum), the second one is decent but forgets the lyrics (second maximum), and the third one is just there to fill the time (third maximum). If there’s no third contestant, you just go back to the superstar. This problem is all about recognizing the talent (or lack thereof) in a group!