Top K Frequent Elements
FreeArrays & hashingMedium5 of 75
The problem
Return the k most frequent distinct integers in a nonempty array. Assume 1 ≤ k ≤ the number of distinct values and that the top-k set is unique. Order does not matter.
Example
nums = [5, 5, 5, 2, 2, 8], k = 2 → [5, 2]
Need a hint?
No frequency can exceed the array length.
Write pseudocode, trace the example, or note an edge case. This scratchpad does not run code.
Notes stay in this browser when storage is available.
Read the solution approach
Count each value, then create frequency buckets from 1 through n. Place each distinct value in its frequency bucket. Walk buckets from largest to smallest, collecting values until k have been selected.
Complexity
O(n) expected time and O(n) space.
Before moving on, explain why the algorithm is correct and trace a boundary case without looking at the approach.