294. Top K Frequent Elements
You are given an integer array nums and an integer k. Return the k values that occur most often in nums.
To make the answer unique, order it from most frequent to least frequent, and when two values are tied on frequency, list the smaller value first. It is guaranteed that k never exceeds the number of distinct values.
The follow-up interviewers care about: can you beat a full O(n log n) sort of the distinct values?
Example 1:
Input: nums = [1, 1, 1, 2, 2, 3], k = 2
Output: [1, 2]
Explanation: 1 appears three times and 2 appears twice — the two most frequent values.
Example 2:
Input: nums = [4, 4, -1, -1, 6], k = 2
Output: [-1, 4]
Explanation: Both -1 and 4 appear twice. They tie on frequency, so the smaller value -1 comes first.
Constraints:
- 1 ≤ nums.length ≤ 10⁵
- -10⁴ ≤ nums[i] ≤ 10⁴
- 1 ≤ k ≤ number of distinct values in nums
Hints:
Count first: a hash map from value to occurrence count reduces the problem to "pick the k entries with the largest counts".
Sorting every distinct value is O(d log d). A min-heap capped at size k evicts the weakest candidate as you go — O(d log k).
A count can never exceed n. Index an array of buckets by count (bucket sort) and read it from the top — no comparison sort of the counts at all.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [1, 1, 1, 2, 2, 3], k = 2
Expected output: [1, 2]