Third Maximum Number
Last Updated: March 31, 2026
Understanding the Problem
This problem asks for the third largest distinct value in the array. The word "distinct" is doing a lot of heavy lifting here. If the array is [2, 2, 3, 1], the three distinct maximums are 3, 2, and 1, not 3, 2, and 2. So duplicates don't count.
There's also a fallback rule: if fewer than three distinct values exist, return the overall maximum. This means we need to handle arrays like [1, 1] (only one distinct value) and [1, 2] (only two distinct values).
The key question is: how do we efficiently track the top three distinct values while scanning the array?
Key Constraints:
1 <= nums.length <= 10^4→ With n up to 10,000, O(n log n) sorting is very comfortable, and even O(n^2) would pass. But the follow-up asks for O(n), so we should aim for a single-pass solution.-2^31 <= nums[i] <= 2^31 - 1→ Full 32-bit integer range. This is critical because it meansInteger.MIN_VALUE(-2^31) is a valid input. Any approach that initializes tracking variables toInteger.MIN_VALUEas a sentinel could mistake a real value for "not set." We need a different way to handle uninitialized state.
Approach 1: Sorting
Intuition
The most natural way to find the third largest distinct value: sort the array in descending order, skip duplicates, and pick the third unique value you encounter. If you run out of unique values before reaching three, return the largest.
This is clean, easy to reason about, and hard to get wrong.
Algorithm
- Sort the array in ascending order.
- Start from the end (largest element) and walk backward.
- Count distinct values as you go. Each time you see a value different from the previous one, increment a counter.
- When the counter reaches 3, return that value.
- If you reach the beginning of the array without finding 3 distinct values, return the largest element (last element after sorting).
Example Walkthrough
Code
- Time Complexity: O(n log n). Sorting dominates. The subsequent linear scan is O(n), but sorting takes O(n log n).
- Space Complexity: O(1) to O(n). Depends on the sorting implementation. In-place sorts use O(log n) stack space, while some languages allocate O(n).
Sorting the entire array just to find 3 values is overkill. What if we tracked only the top 3 distinct values in a single pass?
Approach 2: Track Three Maximums (Optimal)
Intuition
We only need three values: the first, second, and third maximum. Instead of sorting, we can maintain three variables and update them as we scan the array. For each element, we check where it fits among our current top three and shift values down accordingly.
The tricky part is handling two edge cases cleanly. First, duplicates: if the current element equals any of the three maximums, we skip it. Second, initialization: since -2^31 is a valid input, we cannot use it as a "not yet set" sentinel. We use Long.MIN_VALUE (or equivalent) to represent an uninitialized slot, because no 32-bit integer can equal a 64-bit minimum.
The three variables form a sorted "window" of the top distinct values seen so far. By checking from the top down (is it bigger than first? than second? than third?), we guarantee that each new value lands in the correct slot. The cascading shift (third = second, second = first, first = num) preserves the relative ordering of previously tracked values.
The duplicate check at the top is essential. Without it, an input like [1, 1, 1] would shift 1 into all three slots, and we'd incorrectly return 1 as the third maximum when it doesn't actually exist.
Algorithm
- Initialize three variables
first,second,thirdtoLong.MIN_VALUE(or equivalent sentinel that's outside the 32-bit integer range). - For each number in the array:
- If it equals
first,second, orthird, skip it (duplicate). - If it's greater than
first, shift:third = second,second = first,first = num. - Else if it's greater than
second, shift:third = second,second = num. - Else if it's greater than
third, setthird = num. - After the scan, if
thirdis stillLong.MIN_VALUE(never assigned a real value), returnfirst(the maximum). Otherwise, returnthird.
Example Walkthrough
Code
- Time Complexity: O(n). A single pass through the array. Each element requires at most 3 comparisons (duplicate check) plus at most 3 more (position check), so O(1) work per element.
- Space Complexity: O(1). Only three extra variables regardless of input size.