Third Maximum Number

Easy
198.

Third Maximum Number

Third Maximum Number is an easy coding problem on arrays and sorting, asked in Amazon, Google and Bloomberg interviews.

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?

Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var thirdMax = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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

  1. Hint 1

    Distinctness is the trap — [2,2,3,1] must treat the two 2s as one value.

  2. Hint 2

    Deduplicate first, then sort descending and read the third entry.

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

  1. Build the set of distinct values and sort it descending.
  2. 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