Top K Frequent Elements

Problem

Analytics dashboards and autocomplete systems need the most common items from a large event stream. Building an efficient frequency filter - without sorting all distinct values - is the core skill here. Given an integer array, return the k most frequent elements in any order.

Input: nums = [1, 1, 1, 2, 2, 3], k = 2   → [1, 2]
Input: nums = [1], k = 1   → [1]
Input: nums = [4, 4, 4, 6, 6, 1, 1, 1], k = 2   → [4, 1]

Solution

Approach: frequency count plus a size-K min-heap keyed on count.

The problem splits into two phases. First, Counter(nums) tallies how many times each value appears in a single O(n) pass. Second, apply the top-K pattern over the distinct (count, num) pairs: push each pair onto a min-heap and, whenever the heap exceeds K, pop its root. Because the tuple's first field is count, the heap orders by frequency, so the root is always the lowest-frequency survivor - exactly the pair to evict when a more frequent element arrives. After every distinct element has been processed, the heap holds the K highest-frequency pairs, and [num for _, num in min_heap] strips the counts to return just the elements.

Trace [1,1,1,2,2,3], K=2: counts are {1:3, 2:2, 3:1}. Push (3,1) and (2,2) filling the heap, then push (1,3) and immediately pop it - count 1 is the smallest. The heap keeps (2,2) and (3,1), yielding elements 1 and 2.

Edge cases: ordering of the output is not required, so the arbitrary heap order is fine. When K equals the distinct count, no pop fires and every element is returned. An empty input produces an empty Counter and an empty result.

Complexity: O(n + m log K) time, O(m + K) space - n to count, then m distinct pushes each O(log K) against a K-capped heap.