Top K Frequent Elements
Top K Frequent Elements is a medium Arrays & Hashing problem from the Blind 75. The key pattern is counting + ordering, and a good solution runs in O(n log n) time.
Problem
Return the k most frequent integers, ordered by decreasing frequency and then increasing value.
Examples
Example 1
Input
{"nums":[5,5,5,2,2,9],"k":2}Output
[5,2]Example 2
Input
{"nums":[1],"k":1}Output
[1]Example 3
Input
{"nums":[4,4,1,1,7],"k":2}Output
[1,4]Approach
Count occurrences in a map, then order the distinct values by decreasing count and, on ties, increasing value. Take the first k.
| Pattern | Counting + ordering |
|---|---|
| Time | O(n log n) |
| Space | O(n) |
Watch out for
Bucket sort by frequency reaches O(n), but this statement's tie rule still needs each bucket sorted.