Given an integer array nums and an integer k, return the k values that appear most often in nums, in any order. The input is guaranteed to have exactly one valid answer: there is never a tie in frequency at the cutoff between the k-th and (k+1)-th most frequent values.
Examples
Example 1:
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
Explanation: 1 appears three times and 2 twice; 3 appears once and misses the cut.
Example 2:
Input: nums = [1], k = 1
Output: [1]
Example 3:
Input: nums = [4,4,4,6,7,7,7,7], k = 2
Output: [4,7]
Example 4:
Input: nums = [-1,-1,-2], k = 1
Output: [-1]
Constraints
1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
1 <= k <= the number of distinct values in nums
Prerequisites
Hash sets and hash maps — expected O(1) membership and lookup, and what "expected" costs when hashes collide. Array traversal, and the habit of asking what a second pass buys over a nested loop.
How to think about it
1. Count and Sort
Intuition
Count how often each value appears, then sort the distinct values by that count and take k. It is the direct reading, and at these sizes it passes — the sort over DISTINCT values, not the whole array, is the part worth noticing.
Algorithm
1. Build a map from value to its number of occurrences. 2. Sort the distinct values by count, descending. 3. Take the first k. That is the answer: it is accepted in any order.
Time & Space
Time O(d log d) where d is the number of distinct values. Space O(d).
2. Bucket by Frequency Optimal
Intuition
A count cannot exceed the array's length, so frequency is a small integer — and small integers can be indexes. Bucketing values by their count and walking the buckets downward finds the top k without sorting anything, which is what turns O(d log d) into O(n).
Algorithm
1. Count occurrences with a map. 2. Make n+1 buckets; put each value in the bucket matching its count. 3. Walk buckets from the highest count down, collecting values until k are gathered. That is the answer: it is accepted in any order.
Time & Space
Time O(n): the count, the bucketing and the walk down are one pass each. Space O(n) for counts and buckets.