Third Maximum Number — Solution in Python, Java & C++
Third Maximum Number solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Third Maximum Number is an easy coding problem on arrays and sorting, asked in Amazon, Google and Bloomberg interviews.
- Difficulty: Easy
- Topics: Arrays, Sorting
- Asked at: Amazon, Google, Bloomberg
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an integer array nums, return the third distinct maximum value. If it does not exist, return the maximum value instead.
Example 1
Input: nums = [3,2,1]
Output: 1
Explanation: The distinct maxima are 3, 2, 1 — the third is 1.
Example 2
Input: nums = [1,2]
Output: 2
Explanation: There is no third distinct value, so the maximum is returned.
Example 3
Input: nums = [2,2,3,1]
Output: 1
Explanation: Duplicates collapse: the distinct order is 3, 2, 1.
Constraints
1 <= nums.length <= 40-1000 <= nums[i] <= 1000
Follow-up: Can you find it in O(n) time?
Hints for Third Maximum Number
Hint 1
Distinctness is the trap — [2,2,3,1] must treat the two 2s as one value.
Hint 2
Deduplicate first, then sort descending and read the third entry.
Hint 3
For O(n), carry three running maxima and skip any value equal to one you already hold.
How to solve Third Maximum Number
Deduplicate, sort descending, and read the third entry — falling back to the maximum when fewer than three distinct values exist.
Approach
- Build the set of distinct values and sort it descending.
- Return the third element if there are at least three, otherwise the first.
Why it works
"Third maximum" is defined over distinct values, so deduplication must precede the ranking; the fallback rule is spelled out in the statement.
Complexity
- Time —
O(n log n) - Space —
O(n)
Pitfalls
- For O(n), carry three running maxima and skip a value equal to one already held — the sentinel for "unset" must lie outside the int range.
[2,2,3,1]has three distinct values (1 is the answer), but[1,2]does not.
Reference solution
Python
def thirdMax(nums):
distinct = sorted(set(nums), reverse=True)
return distinct[2] if len(distinct) >= 3 else distinct[0]Java
public static int thirdMax(int[] nums) {
TreeSet<Integer> distinct = new TreeSet<>();
for (int x : nums) distinct.add(x);
if (distinct.size() < 3) return distinct.last();
Iterator<Integer> it = distinct.descendingIterator();
it.next();
it.next();
return it.next();
}C++
int thirdMax(vector<int>& nums) {
set<int> distinct(nums.begin(), nums.end());
vector<int> ordered(distinct.rbegin(), distinct.rend());
return ordered.size() >= 3 ? ordered[2] : ordered[0];
}JavaScript
var thirdMax = function(nums) {
const distinct = Array.from(new Set(nums)).sort(function(a, b) { return b - a; });
return distinct.length >= 3 ? distinct[2] : distinct[0];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms