Third Maximum Number

Third Maximum Number

What is this problem about?

Finding the maximum value in an array is trivial, but what about the third distinct maximum? "Third Maximum Number" asks you to find the third-largest unique number in an array. If there are fewer than three distinct numbers, the problem typically asks you to return the maximum number instead.

Why is this asked in interviews?

This Third Maximum Number interview question is a classic "easy" problem asked by top companies like Apple, Microsoft, and Google. It tests your ability to handle distinctness and track multiple variables simultaneously. While sorting is an easy way to solve it, interviewers often look for a linear O(n) solution to see if you can avoid the O(n log n) cost of a full sort.

Algorithmic pattern used

This problem follows the Array, Sorting interview pattern.

1. O(n log n) approach: Remove duplicates (using a set), sort the unique numbers, and return the third-to-last element (or the last if length < 3).
2. O(n) approach: Use three variables (first, second, third) initialized to a value smaller than any possible input (or use null/None). Iterate through the array once:
   • If the current number is already equal to one of the variables, skip it (distinctness).
   • If it's larger than first, shift all three variables down.
   • Else if it's larger than second, shift second and third down.
   • Else if it's larger than third, update third.
3. Return third if it was updated, else return first.

Example explanation

Array: [3, 2, 2, 1]

1. Initial: first=null, second=null, third=null.
2. See 3: first=3.
3. See 2: second=2, first=3.
4. See 2: Skip (already have 2).
5. See 1: third=1, second=2, first=3. Result: 1. If the array was [1, 2], the result would be 2 (the max).

Common mistakes candidates make

In "Third Maximum Number coding problem," many candidates forget to handle duplicate numbers, incorrectly returning the third element of a sorted list even if it's a repeat of the second. Another error is not correctly handling the "return the max if no third max exists" rule. Using a value like Integer.MIN_VALUE for initialization can also be risky if that value is actually present in the input array.

Interview preparation tip

When tracking the "top K" elements of an array, always consider if you need a full sort or just a fixed set of variables. For small K (like 3), variables are much more efficient. For larger K, a min-heap is the standard tool. Always be clear about whether you are dealing with "distinct" values or not.