Third Maximum Number
Easy · Arrays & Hashing · Array · Sorting
Problem
You are given an integer array nums. Return the third largest distinct value in it. If nums holds fewer than three distinct values, return the largest value instead.
Equal values count once: [5, 5, 4] has only two distinct values, so its answer is 5. Aim for a single pass that keeps the three largest distinct values seen so far.
Examples
Input: nums = [4,9,1,7] Output: 4
The distinct values from largest down are 9, 7, 4, 1, so the third is 4.
Input: nums = [8,3] Output: 8
Only two distinct values exist, so the largest, 8, is returned.
Input: nums = [6,6,5,5,2] Output: 2
The distinct values are 6, 5 and 2; the repeated 6 and 5 do not take extra places.
Constraints
- 1 <= len(nums) <= 10^4
- -2^31 <= nums[i] <= 2^31 - 1
Approaches
- Sort the distinct values — time O(n log n), space O(n)
Follow-up
What if the values arrive as a stream and you are asked for the third maximum after each one? The three slots already answer that: each new value updates them in O(1), and the answer after any prefix is read off the slots.
Related problems
Start free on Cariara · Coding problems · System design studio
