Third Maximum Number Leetcode Solution

Problem Statement

Third Maximum Number Leetcode Solution – Given an integer array nums, return the third distinct maximum number in this array. If the third maximum does not exist, return the maximum number.

Example

Input:

 nums = [3,2,1]

Output:

 1

Explanation:

The first distinct maximum is 3.
The second distinct maximum is 2.
The third distinct maximum is 1.

Input:

 nums = [2,2,3,1]

Output:

 1

Explanation:

The first distinct maximum is 3.
The second distinct maximum is 2 (both 2's are counted together since they have the same value).
The third distinct maximum is 1.

Approach

This is a simple solution that keeps track of 3 values and updates all the necessary values when a larger number is seen. In the first case, if the value is bigger than the maxValue1, the other values need to be updated first (pushing things downward).

In addition, we need to ensure that the new value won’t be the same as one of the bigger values, which causes duplicate (highest) values.

Finally, I have a check to see whether the number of elements is less than 3. If so, return the highest value. Otherwise, return the 3rd max number.

Idea:

The key idea is to keep 3 variables to store the maximum three elements from the array, let’s say mx1,mx2, and mx3 are the three variables where mx1 denotes the first maximum, mx2 denotes the second maximum, and mx3 denotes the third maximum.

Now we traverse the array,

1. if we find a number greater than mx1, then we will update mx1 but the catch here is since the value of mx1 is changing here so we need to store the previous value of mx1 to mx2, now mx2 will also change from here so we store the previous value of mx2 to mx3.
2. If we find a number greater than mx2, and not equal to mx1 then we need to update mx2 but here also, we need to store the previous value of mx2 to mx3.
3. If we find a number greater than mx3,  and not equal to mx1 and mx2 we update mx3.

Code

C++ Code for Third Maximum Number

class Solution {
public:
    int thirdMax(vector<int>& nums) {
        int n = nums.size();
        
        long long int mx1 = -1e15;
        long long int mx2 = -1e15;
        long long int mx3 = -1e15;
        
        for(int i=0;i<n;i++){
            if(nums[i] > mx1){
                mx3 = mx2;
                mx2 = mx1;
                mx1 = nums[i];
            }
            else if(nums[i] > mx2 && nums[i]!=mx1){
                mx3 = mx2;
                mx2 = nums[i];
            }
            else if(nums[i] > mx3 && nums[i]!=mx1 && nums[i]!=mx2){
                mx3 = nums[i];
            }
        }
        
        return mx3==-1e15 ? mx1 : mx3;   
    }
};

Java Code for Third Maximum Number

class Solution{
    public int thirdMax(int[] nums) {
        Integer max1 = null;
        Integer max2 = null;
        Integer max3 = null;
        for (Integer n : nums) {
            if (n.equals(max1) || n.equals(max2) || n.equals(max3)) continue;
            if (max1 == null || n > max1) {
                max3 = max2;
                max2 = max1;
                max1 = n;
            } else if (max2 == null || n > max2) {
                max3 = max2;
                max2 = n;
            } else if (max3 == null || n > max3) {
                max3 = n;
            }
        }
        return max3 == null ? max1 : max3;
    }
}

Complexity Analysis For Third Maximum Number Leetcode Solution

Time Complexity

Since we are traversing the whole array only once, so the time complexity is O(n).

Space Complexity

We are only using three variables8, so the space complexity is O(1).