##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/414.html

# 414. Third Maximum Number

Easy

## Description

Given a non-empty array of integers, return the third maximum number in this array. If it does not exist, return the maximum number. The time complexity must be in O(n).

Example 1:

Input: [3, 2, 1]

Output: 1

Explanation: The third maximum is 1.

Example 2:

Input: [1, 2]

Output: 2

Explanation: The third maximum does not exist, so the maximum (2) is returned instead.

Example 3:

Input: [2, 2, 3, 1]

Output: 1

Explanation: Note that the third maximum here means the third maximum distinct number. Both numbers with value 2 are both considered as second maximum.

## Solution

Use three variables to store the three distinct maximum numbers. Also use a variable to store the count of distinct numbers in the array. Initially, the three variables for three maximum numbers are Long.MIN_VALUE, where data type long is used to avoid overflow.

Loop over the array. Use the idea of insertion sort and update the three distinct maximum numbers. If the current number is greater than at least one of the three distinct maximum numbers, then update the distinct maximum numbers that has a smaller value, and increase the counter by 1.

Finally, if the counter is greater than or equal to 3, return the third distinct maximum number. Otherwise, return the first maximum number.

• class Solution {
public int thirdMax(int[] nums) {
if (nums == null || nums.length == 0)
return 0;
long firstMax = Long.MIN_VALUE;
long secondMax = Long.MIN_VALUE;
long thirdMax = Long.MIN_VALUE;
int count = 0;
for (int num : nums) {
long numLong = (long) num;
if (numLong == firstMax || numLong == secondMax || numLong == thirdMax)
continue;
if (numLong > firstMax) {
thirdMax = secondMax;
secondMax = firstMax;
firstMax = numLong;
count++;
} else if (numLong > secondMax) {
thirdMax = secondMax;
secondMax = numLong;
count++;
} else if (numLong > thirdMax) {
thirdMax = numLong;
count++;
}
}
return count >= 3 ? (int) thirdMax : (int) firstMax;
}
}

• 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

############

class Solution(object):
def thirdMax(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
first = second = third = float("-inf")
for num in nums:
if num in [first, second, third]:
continue
if num > first:
third = second
second = first
first = num
elif num > second:
third = second
second = num
elif num > third:
third = num
return third if third != float("-inf") else first


• 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);
}
};

• func thirdMax(nums []int) int {
m1, m2, m3 := math.MinInt64, math.MinInt64, math.MinInt64
for _, num := range nums {
if num == m1 || num == m2 || num == m3 {
continue
}
if num > m1 {
m3, m2, m1 = m2, m1, num
} else if num > m2 {
m3, m2 = m2, num
} else if num > m3 {
m3 = num
}
}
if m3 != math.MinInt64 {
return m3
}
return m1
}