Most Frequent Values, Ranked
MediumArrays & Hashing
Problem
A music service logs the ID of every song played today. The trending panel shows the k songs that were played most often.
Given nums and k, return the k values with the highest frequencies, ordered from most to least frequent. When two values have the same frequency, the smaller value ranks first (both for ordering and for deciding who makes the cut).
Example 1
- Input:
- nums = [4, 4, 1, 1, 1, 7, 9, 9], k = 2
- Output:
- [1, 4]
Frequencies: 1 → 3, 4 → 2, 9 → 2, 7 → 1. 1 is first; 4 and 9 tie at 2 and the smaller, 4, takes the second slot.
Example 2
- Input:
- nums = [5, 3, 5, 3, 8], k = 1
- Output:
- [3]
3 and 5 both appear twice; 3 is smaller.
Constraints
- 1 ≤ nums.length ≤ 10^5
- -10^4 ≤ nums[i] ≤ 10^4
- 1 ≤ k ≤ number of distinct values in nums
Hint
Show the first hint
Start by computing how often each value appears.
Walkthrough
How to approach it
01Clarify before coding
- How are ties broken? By smaller value first; this makes the answer unique.
- Is the output order significant? Yes: most frequent first, ties by ascending value.
- Is k always valid? Yes, at most the number of distinct values.
02Brute force
Count frequencies, then sort the distinct values by (frequency descending, value ascending) and take the first k.
Cost: O(n + d log d) where d is the number of distinct values: acceptable, but the sort is the part an interviewer will ask you to remove.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.