341. Third Maximum Number
Given an integer array nums, find the third-largest distinct value in it. Duplicates collapse: in [2, 2, 3, 1] the distinct values are {3, 2, 1}, so the third maximum is 1, not 2.
If the array holds fewer than three distinct values, return the overall maximum instead.
Return a single integer either way. Can you do it in one pass without sorting?
Example 1:
Input: nums = [3, 2, 1]
Output: 1
Explanation: The distinct values ranked high to low are 3, 2, 1 — the third one is 1.
Example 2:
Input: nums = [1, 2]
Output: 2
Explanation: Only two distinct values exist, so the rule falls back to the maximum, 2.
Example 3:
Input: nums = [2, 2, 3, 1]
Output: 1
Explanation: The repeated 2 counts once. Distinct values are {3, 2, 1}, whose third largest is 1.
Constraints:
- 1 ≤ nums.length ≤ 10⁴
- -2³¹ ≤ nums[i] ≤ 2³¹ - 1
Hints:
Deduplicate first (a set), then you only need the three biggest distinct values — a full sort works, but even that is more than necessary.
Track a podium: first, second, third. For each x, skip it if it already equals one of them; otherwise let it displace the right slot and shift the rest down. Beware using a sentinel like INT_MIN for "empty" — INT_MIN is a legal array value, so prefer null/None or a wider type.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [3, 2, 1]
Expected output: 1