Third Maximum Number Leetcode Solution

As the title says, the goal is to find the third maximum integer in a given array of integers. Note that we need to find the distinct third maximum integer in the array. We return the maximum integer in the array when it has no distinct third maximum integer.

Table of Contents

Example

Array = {1 , 3 , 2 , -2 , -4 , -9}

Explanation

The first maximum is 3, second maximum is 2 and third maximum is 1. So, we print 1.

Array = {1 , 1 , 3}

Explanation

The first maximum is 3, second maximum is 1, but there is no third maximum because we consider both the 1s as the second maximum here.

Approach(Sorting)

We can sort the whole array and find the third distinct integer starting from its back. Note that we can’t return Array[N – 3] simply as there can be duplicate entries in the array. If we do not find 3 distinct integers in the array, we return its last element as it is the maximum element. Follow the given algorithm for better understanding.

Algorithm

Create a function thirdMax() returning the required integer
thirdMax() returns the third distinct maximum integer in a given array- a
Sort the array
Initialize a variable, idx to store the last index of the array and distinctCount to count the distinct elements from the back
while idx >= 0:
- Increment distinctCount
- Initialize i to iterate through indices having the same value as a[idx]
- while the elements before idx have the same value as a[idx] and i >= 0:
  - Decrement i
- If i == -1, it means that we have traversed the whole array
  - Return a[n – 1], maximum element as there were not even 3 three distinct elements in the array
- Assign idx = i to jump to next set of maximum integers
- If distinctCount is equal to 2,
  - it means we have checked 2 bigger elements than the current element(a[idx])
  - Return current element, a[idx]
For sake of function syntax, return -1.
Print the result

Implementation of Third Maximum Number Leetcode Solution

C++ Program

#include <bits/stdc++.h>
using namespace std;

int thirdMax(vector <int> &a)
{
    int n = a.size();
    sort(a.begin() , a.end());

    int idx = n - 1 , i , distinctCount = 0;

    while(idx >= 0)
    {
        distinctCount++;
        i = idx - 1;
        //to check all the values with same value as a[idx]
        while(i >= 0 && a[i] == a[idx])
            i--;

        //no third distinct element
        if(i == -1)
            return a[n - 1];
        idx = i;

        //found 2 bigger elements before?
        if(distinctCount == 2)
            return a[idx];
    }
    return -1;
}

int main()
{
    vector <int> a = {1 , 3 , 2 , -2 , -4 , -9};
    cout << thirdMax(a) << '\n';
}

Java Program

import java.util.Arrays;

class third_max
{
    public static void main(String args[])
    {
        int[] a = {1 , 3 , 2 , -2 , -4 , -9};
        System.out.println(thirdMax(a));
    }

    static int thirdMax(int[] a)
    {
        int n = a.length;
        Arrays.sort(a);

        int idx = n - 1 , i , distinctCount = 0;

        while(idx >= 0)
        {
            distinctCount++;
            i = idx - 1;
            //to check all the values with same value as a[idx]
            while(i >= 0 && a[i] == a[idx])
                i--;

            //no third distinct element
            if(i == -1)
                return a[n - 1];
            idx = i;

            //found 2 bigger elements before?
            if(distinctCount == 2)
                return a[idx];
        }
        return -1;
    }
}

Complexity Analysis of Third Maximum Number Leetcode Solution

Time Complexity

O(NlogN), N = size of the array, as we sort the whole array.

Space complexity

O(1) as we use only constant memory space.

Approach(Optimal)

The optimal approach here is to maintain just three values that will store the first, second and third maximum integers in the array. However, there are some base cases such as we always have to consider distinct elements as maximum. For this purpose, set can be used so that we can always get rid of duplicate elements. We can iterate through the array and maintain the size of set as 3 after every iteration. In case it contains more than 3 elements after any insertion, we pop out the least element from it so that it contains the three distinct largest elements in the end. If its size is less than 3 in the end, we return its maximum value.