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}

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.

### 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*

- Decrement
- 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]

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

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

- Again we use the same function
**thirdMax()**to solve our problem - Initialize a set to store maximum integers.
- 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

- If the size of the set is equal to 3
- return the least element from it

- Else
- return the maximum element in it

- 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.