Third Maximum Number
Understanding the Problem
This problem asks for the third largest distinct value in the array. The word "distinct" carries the weight here. For the array [2, 2, 3, 1], the three distinct maximums are 3, 2, and 1, not 3, 2, and 2. Duplicates do not count.
There is also a fallback rule: if fewer than three distinct values exist, return the overall maximum. So arrays like [1, 1] (one distinct value) and [1, 2] (two distinct values) both return their largest element.
The task reduces to tracking the top three distinct values during a scan of the array.
Key Constraints:
1 <= nums.length <= 10^4→ With n up to 10,000, O(n log n) sorting runs comfortably, and even O(n^2) would pass. The follow-up asks for O(n), which points toward a single-pass solution.-2^31 <= nums[i] <= 2^31 - 1→ Full 32-bit integer range, which meansInteger.MIN_VALUE(-2^31) is itself a valid input. An approach that initializes its tracking variables toInteger.MIN_VALUEas a sentinel cannot distinguish a real -2^31 from "not yet set." Uninitialized state needs a value outside the 32-bit range.
Approach 1: Sorting
Intuition
Sort the array, then scan from the largest element toward the smallest, counting distinct values as you pass them. The third distinct value reached is the answer. If fewer than three distinct values exist, the count never reaches three, and the largest element is returned instead.
Sorting groups equal values into adjacent runs, so a value differs from a distinct maximum exactly when it differs from its neighbor in the sorted order. That makes the distinct count a single comparison per element.
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 does O(n log n) work to surface three values. The next approach tracks only those three values in a single pass, dropping the cost to O(n).
Approach 2: Track Three Maximums (Optimal)
Intuition
Only three values matter: the first, second, and third distinct maximum. Instead of sorting, maintain three variables and update them during a single scan. For each element, find where it fits among the current top three and shift the lower values down.
Two edge cases need care. Duplicates: if the current element equals any of the three maximums, skip it so the same value cannot occupy two slots. Initialization: since -2^31 is a valid input, it cannot serve as a "not yet set" sentinel. Use Long.MIN_VALUE (or the equivalent) for an uninitialized slot, since no 32-bit integer can equal a 64-bit minimum.
The invariant is that first >= second >= third always holds and the three variables are the largest distinct values seen so far. Testing a new value from the top down (greater than first? than second? than third?) places it in the highest slot it qualifies for, and the cascading shift (third = second, second = first, first = num) pushes the displaced values down by one rank, which preserves the ordering.
The duplicate check is what keeps the three slots distinct. Without it, an input like [1, 1, 1] would shift 1 into all three slots and return 1 as the third maximum even though only one distinct value exists.
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.