Third Maximum Number Solution in Java

Explore More Solutions:

Code Solution


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

Problem Description

Ah, the classic dilemma of finding the third maximum number in an array. It’s like trying to find the third best pizza in a city where every corner has a pizzeria. You know there’s a top dog (the best pizza), a solid runner-up (the second best), and then there’s that third one that you can’t quite remember the name of but you know it exists.

In this LeetCode problem, you’re given an array of integers, and your task is to find the third distinct maximum number. If it doesn’t exist, you simply return the maximum number. So, if you have an array like [3, 2, 1], the answer is 1. But if you have [1, 2], you just go with 2 because the third one is MIA.

Approach Explanation

The code provided uses three variables (max1, max2, and max3) to keep track of the first, second, and third maximum numbers, respectively. It iterates through the array, updating these variables as it finds larger numbers. If a number is greater than max1, it shifts the values down the line. If it’s between max1 and max2, it updates max2, and if it’s between max2 and max3, it updates max3.

At the end of the loop, if max3 is still at its initialized value, it means there wasn’t a third distinct maximum, so it returns max1.

Time and Space Complexity

Complexity	Details
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 the three maximum variables.

Real-World Example

Imagine you’re at a talent show, and there are three contestants who can sing like angels. The judges are trying to decide who gets the third place. If one contestant is clearly better than the others, they get the first place. The second place goes to the next best singer. But what if the third singer is just a little off-key? If they don’t stand out, the judges might just give the third place to the second best singer instead. This is exactly what our code does!