# Third Maximum Number
**Difficulty:** EASY
[External](https://leetcode.com/problems/third-maximum-number)
Canonical: https://scaleengineer.com/dsa/problems/third-maximum-number
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
---
## Problem
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 1:**

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

**Example 2:**

**Input:** nums = [1,2]
**Output:** 2
**Explanation:**
The first distinct maximum is 2.
The second distinct maximum is 1.
The third distinct maximum does not exist, so the maximum (2) is returned instead.

**Example 3:**

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

**Constraints:**

* `1 <= nums.length <= 104`
* `-231 <= nums[i] <= 231 - 1`

**Follow up:** Can you find an `O(n)` solution?

# Approaches
## Sorting Approach
This approach involves sorting the array first. Once sorted, the distinct maximums can be found by iterating from the end of the array.
**Time:** O(N log N), where N is the number of elements in the array. The dominant operation is sorting the array. · **Space:** O(log N) or O(N) depending on the implementation of the sorting algorithm. In Java, `Arrays.sort()` for primitives uses a variant of Quicksort which has an average space complexity of O(log N) for the recursion stack.
**Pros:** Simple to understand and implement.; Leverages standard library functions.
**Cons:** Not the most efficient in terms of time complexity due to the sorting step.; Modifies the input array, which might not be desirable in some contexts.
### Explanation
The core idea is that after sorting the array in ascending order, the largest elements will be at the end. We can then iterate from the end of the sorted array, keeping track of the distinct numbers we encounter. The first distinct number from the end is the maximum, the second is the second maximum, and the third is the third maximum. If we traverse the entire array and find fewer than three distinct numbers, we return the overall maximum.

```java
import java.util.Arrays;

class Solution {
    public int thirdMax(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        
        // The maximum element is always at the end after sorting
        int max = nums[n - 1];
        
        int distinctCount = 1;
        // Iterate from the second to last element
        for (int i = n - 2; i >= 0; i--) {
            // If we find a new smaller element, it's a new distinct maximum
            if (nums[i] < nums[i + 1]) {
                distinctCount++;
            }
            // If we have found 3 distinct maximums, the current element is the third one
            if (distinctCount == 3) {
                return nums[i];
            }
        }
        
        // If we finish the loop and haven't found 3 distinct maximums,
        // it means the third maximum doesn't exist. Return the overall maximum.
        return max;
    }
}
```
### Algorithm
- Sort the input array `nums` in non-decreasing order.
- Iterate through the sorted array from right to left to find distinct elements.
- Use a counter `distinctCount` to track the number of distinct maximums found.
- The first element from the end is the first maximum. Increment `distinctCount`.
- Continue iterating backwards. If the current element is smaller than the previous one (from the right), it's a new distinct maximum. Increment `distinctCount`.
- If `distinctCount` reaches 3, the current element is the third maximum. Return it.
- If the loop completes and `distinctCount` is less than 3, it means a third maximum does not exist. In this case, return the largest element in the array (the last element of the sorted array).

## Set-based Approach
This approach uses a `Set` data structure to efficiently store only the unique elements from the input array. After populating the set, we can easily find the third maximum.
**Time:** O(N). Populating the set takes O(N) time. Finding and removing the maximums from the set takes time proportional to the number of unique elements (K), which is at most N. So, the total time is O(N). · **Space:** O(K), where K is the number of distinct elements in the array. In the worst case, all elements are distinct, so the space complexity is O(N).
**Pros:** More efficient than the sorting approach in terms of time complexity.; Conceptually straightforward.
**Cons:** Requires extra space to store the unique elements, which can be up to O(N).
### Explanation
First, we iterate through the input array `nums` and add each element to a `HashSet`. The `HashSet` automatically handles duplicates, so after the iteration, it will contain all the unique numbers from the array.
Then, we check the size of the set. If the size is less than 3, it's impossible to have a third maximum, so we find and return the maximum element in the set.
If the size is 3 or more, we can find the third maximum by repeatedly finding and removing the largest element from the set. We remove the largest element, then remove the new largest element. The largest element remaining in the set will be the third distinct maximum.

```java
import java.util.HashSet;
import java.util.Set;
import java.util.Collections;

class Solution {
    public int thirdMax(int[] nums) {
        Set<Integer> distinctNums = new HashSet<>();
        for (int num : nums) {
            distinctNums.add(num);
        }

        // If there are fewer than 3 distinct numbers, return the maximum.
        if (distinctNums.size() < 3) {
            return Collections.max(distinctNums);
        }

        // Remove the first maximum
        distinctNums.remove(Collections.max(distinctNums));
        // Remove the second maximum
        distinctNums.remove(Collections.max(distinctNums));
        
        // The remaining maximum is the third maximum
        return Collections.max(distinctNums);
    }
}
```
### Algorithm
- Create a `HashSet` to store unique elements.
- Iterate through the `nums` array and add each number to the set.
- Check the size of the set. If it's less than 3, find the maximum element in the set and return it.
- If the set size is 3 or more, find and remove the maximum element.
- Find and remove the new maximum element.
- The largest remaining element in the set is the third maximum. Return it.

## Single Pass with Constant Space
This is the most optimal approach, solving the problem in a single pass through the array with constant extra space. It involves maintaining three variables to track the top three distinct maximums seen so far.
**Time:** O(N), as we iterate through the array only once. · **Space:** O(1), as we only use a fixed number of extra variables regardless of the input size.
**Pros:** Optimal time complexity of O(N).; Optimal space complexity of O(1).; Does not modify the input array.
**Cons:** The logic can be slightly more complex to write correctly due to handling nulls and multiple conditions.
### Explanation
We use three variables, `max1`, `max2`, and `max3`, to store the first, second, and third distinct maximums. To handle the edge case where `Integer.MIN_VALUE` is one of the maximums, we can use nullable `Integer` objects, initializing them to `null`.
We iterate through the input array `nums` once. For each number, we first check if it's a duplicate of the numbers already stored in `max1`, `max2`, or `max3`. If it is, we skip it. Otherwise, we compare the number with `max1`, `max2`, and `max3` and update them accordingly:
- If the number is greater than `max1`, it becomes the new `max1`, and the old `max1` and `max2` are shifted down to `max2` and `max3`.
- If the number is not greater than `max1` but is greater than `max2`, it becomes the new `max2`, and the old `max2` is shifted to `max3`.
- If the number is not greater than `max1` or `max2` but is greater than `max3`, it becomes the new `max3`.
After the loop, if `max3` is still `null`, it means we found fewer than three distinct numbers, so we return `max1` (the overall maximum). Otherwise, we return `max3`.

```java
class Solution {
    public int thirdMax(int[] nums) {
        Integer max1 = null;
        Integer max2 = null;
        Integer max3 = null;

        for (Integer num : nums) {
            // Skip duplicates
            if (num.equals(max1) || num.equals(max2) || num.equals(max3)) {
                continue;
            }

            if (max1 == null || num > max1) {
                max3 = max2;
                max2 = max1;
                max1 = num;
            } else if (max2 == null || num > max2) {
                max3 = max2;
                max2 = num;
            } else if (max3 == null || num > max3) {
                max3 = num;
            }
        }

        // If max3 is null, it means there are fewer than 3 distinct numbers.
        // In this case, return the overall maximum, which is max1.
        return max3 == null ? max1 : max3;
    }
}
```
### Algorithm
- Initialize three nullable `Integer` variables: `max1`, `max2`, `max3` to `null`.
- Iterate through each `num` in the `nums` array.
- If `num` is equal to any of `max1`, `max2`, or `max3`, continue to the next iteration to skip duplicates.
- If `max1` is `null` or `num > max1`, update the maximums: `max3 = max2`, `max2 = max1`, `max1 = num`.
- Else if `max2` is `null` or `num > max2`, update: `max3 = max2`, `max2 = num`.
- Else if `max3` is `null` or `num > max3`, update: `max3 = num`.
- After the loop, check if `max3` is `null`. If it is, return `max1`. Otherwise, return `max3`.

# Solutions
### Java

```java
class Solution {
public
  int thirdMax(int[] nums) {
    long m1 = Long.MIN_VALUE;
    long m2 = Long.MIN_VALUE;
    long m3 = Long.MIN_VALUE;
    for (int num : nums) {
      if (num == m1 || num == m2 || num == m3) {
        continue;
      }
      if (num > m1) {
        m3 = m2;
        m2 = m1;
        m1 = num;
      } else if (num > m2) {
        m3 = m2;
        m2 = num;
      } else if (num > m3) {
        m3 = num;
      }
    }
    return (int)(m3 != Long.MIN_VALUE ? m3 : m1);
  }
}

```

### CPP

```cpp
class Solution {
public:
  int thirdMax(vector<int> &nums) {
    long m1 = LONG_MIN, m2 = LONG_MIN, m3 = LONG_MIN;
    for (int num : nums) {
      if (num == m1 || num == m2 || num == m3)
        continue;
      if (num > m1) {
        m3 = m2;
        m2 = m1;
        m1 = num;
      } else if (num > m2) {
        m3 = m2;
        m2 = num;
      } else if (num > m3) {
        m3 = num;
      }
    }
    return (int)(m3 != LONG_MIN ? m3 : m1);
  }
};

```

### Python

```python
class Solution:
    def thirdMax(self, nums: List[int]) -> int: m1 = m2 = m3 = - inf for num in nums: if num in [m1, m2, m3]: continue if num > m1: m3, m2, m1 = m2, m1, num elif num > m2: m3, m2 = m2, num elif num > m3: m3 = num return m3 if m3 != - inf else m1

```