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.

Example 1:

Input: nums = [5, 5, 5, 3, 3, 7], k = 2
Output: [5, 3]
Explanation: 5 appears 3 times and 3 appears twice, more than any other element.

Example 2:

Input: nums = [8], k = 1
Output: [8]

Example 3:

Input: nums = [6, 6, 6, 9, 9, 2, 2, 2], k = 2
Output: [6, 2]
Explanation: 2 and 6 each appear 3 times; the order of the answer does not matter.

Constraints:

• 1 <= nums.length <= 10^4
• -100 <= nums[i] <= 100
• k is in the range [1, the number of unique elements in the array].
• It is guaranteed that the answer is unique.

Solution Breakdown

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 [5,5,5,3,3,7], K=2: counts are {5:3, 3:2, 7:1}. Push (3,5) and (2,3) filling the heap, then push (1,7) and immediately pop it - count 1 is the smallest. The heap keeps (2,3) and (3,5), yielding elements 5 and 3.

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.