Top K Frequent Elements
Module 19 · Heaps
Problem
Given an integer array nums and an integer k, return the k most
frequent elements. The answer may be in any order; the test guarantees it
is unique.
Examples
Example 1
nums = [1,1,1,2,2,3], k = 2Output[1, 2]Explanation. 1 appears ×3, 2 appears ×2, 3 appears ×1 — top two are 1 and 2
Example 2
nums = [1], k = 1Output[1]Constraints
1 ≤ n ≤ 10⁵, k is between 1 and the number of distinct values, values in ±10⁴.
Attempt it first
Step one is unavoidable and cheap: count how often each value appears (a
hash map, Module 6 — one O(n) pass). The real question is step two. You
now have m distinct values with their counts and you want the k with
the highest counts. Before reading on, decide: do you need to fully
order all m values by frequency to name the top k? Sorting them is one
option — what does it cost, and can you do better when k is much smaller
than m?