Third Maximum Number Leetcode Solution


Difficulty Level Easy
Frequently asked in Amazon Facebook Google
Array

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.

Example

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

Explanation

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

Array = {1 , 1 , 3}
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.

Third Maximum Number Leetcode Solution

Algorithm

  1. Create a function thirdMax() returning the required integer
  2. thirdMax() returns the third distinct maximum integer in a given array- a
  3. Sort the array
  4. Initialize a variable, idx to store the last index of the array and distinctCount to count the distinct elements from the back
  5. while idx >= 0:
    • Increment distinctCount
    • Initialize 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]
  6.  For sake of function syntax, return -1.
  7. 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;
    }
}
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.

Algorithm

  1. Again we use the same function thirdMax() to solve our problem
  2. Initialize a set to store maximum integers.
  3. For every element in the array:
    • Add it to the set
    • If the size of the set exceeds 3
      • Erase/Remove the least element in the set
  4. If the size of the set is equal to 3
    • return the least element from it
  5. Else
    • return the maximum element in it
  6. Print the result

Implementation of Third Maximum Number Leetcode Solution

C++ Program

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

int thirdMax(vector <int> &a)
{
    set <int> maxElements;
    for(int &element : a)
    {
        maxElements.insert(element);
        if(maxElements.size() > 3)
            maxElements.erase(*maxElements.begin());
    }
    if(maxElements.size() == 3)
        return *maxElements.begin();

    return *prev(maxElements.end());
}

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

Java Program

import java.util.*;

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)
    {
        Set <Integer> maxElements = new HashSet <>();
        for(int element : a)
        {
            maxElements.add(element);
            if(maxElements.size() > 3)
                maxElements.remove(Collections.min(maxElements));
        }

        if(maxElements.size() == 3)
            return Collections.min(maxElements);
        return Collections.max(maxElements);
    }
}
1

Complexity Analysis of Third Maximum Number Leetcode Solution

Time Complexity

O(N) as we iterate through the array in a single pass. The deletion and insertion of elements in the set take constant time, as we maintain a maximum of 3 elements in it after every iteration. Here, N = size of the array.

Space complexity

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