Given an array and k, return the k most frequent elements, in any order. The answer is guaranteed to be unique.
Before you code
This is two steps: count each value, then pick the top k counts. The second step is exactly the size-k heap.
Hints
- Count with a hash map (
collections.Counter). - Keep a min-heap of
(count, value)with at most k entries: O(n log k). - Linear alternative: bucket the values by count (a list of lists indexed by frequency, up to n) and read buckets from the highest down.
Production & complexity notes
When solving Top k frequent elements on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Top-k and merging streams to reinforce the underlying pattern.
What it practices
Top k over derived values, from Top-k and merging streams.