Third Maximum Number
Easy · Arrays & Hashing · Explanation and code example
Three Distinct Maximum Candidates
How it works
Maintain the largest, second-largest, and third-largest distinct values seen so far. Insert a new distinct value into its rank and shift lower candidates. If fewer than three distinct values exist, return the largest value instead.
Steps
- Initialize three candidate slots below every valid value.
- Insert each value at its distinct rank, shifting candidates as needed.
- Return third when it exists, otherwise first.
Complexity
- Time: O(n).
- Space: O(1).
Things to watch for
- Repeated copies of a maximum do not occupy multiple ranks.
- The sentinel must be below INT_MIN in C++.
- Fewer than three distinct values returns the maximum.
Python code example
import math
class Solution:
def thirdMax(self, nums: list[int]) -> int:
max1 = -math.inf # the maximum
max2 = -math.inf # the second maximum
max3 = -math.inf # the third maximum
for num in nums:
if num > max1:
max3 = max2
max2 = max1
max1 = num
elif max1 > num and num > max2:
max3 = max2
max2 = num
elif max2 > num and num > max3:
max3 = num
return max1 if max3 == -math.inf else max3
C++ code example
class Solution {
public:
int thirdMax(vector<int>& nums) {
long max1 = LONG_MIN; // the maximum
long max2 = LONG_MIN; // the second maximum
long max3 = LONG_MIN; // the third maximum
for (const int num : nums)
if (num > max1) {
max3 = max2;
max2 = max1;
max1 = num;
} else if (max1 > num && num > max2) {
max3 = max2;
max2 = num;
} else if (max2 > num && num > max3) {
max3 = num;
}
return max3 == LONG_MIN ? max1 : max3;
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.