Top K Frequent Elements

Find the k most frequent integers in a list using a heap-based approach.

heap frequency counter top-k

Write a function `top_k_frequent(nums, k)` that takes a non-empty list of integers `nums` and an integer `k` (1 ≤ k ≤ number of distinct elements in `nums`) and returns a list of the `k` most frequent elements. The returned list must be ordered by decreasing frequency. If two elements have the same frequency, the element with the larger numeric value must come first. The returned list must contain exactly `k` elements. Your solution must have a time complexity better than O(n log n), ideally O(n log k) using a heap, where n is the length of `nums`.

Constraints

1 ≤ len(nums) ≤ 10^5
-10^9 ≤ nums[i] ≤ 10^9
1 ≤ k ≤ number of distinct elements in nums

Time complexity should be O(n log k) or better. Space complexity O(n) for frequency counting.

Example

```python
>>> top_k_frequent([1,1,1,2,2,3], 2)
[1, 2]
>>> top_k_frequent([1], 1)
[1]
>>> top_k_frequent([4,4,4,4], 1)
[4]
>>> top_k_frequent([6,5,4,3,2,1], 3)
[6, 5, 4]  # all frequency 1, descending value
>>> top_k_frequent([1,1,2,2,3,3], 2)
[3, 2]  # tie on frequency, larger value first
```

20 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Count the frequency of each number using a dictionary or collections.Counter.

Use a min-heap of size k to keep the k elements with the highest frequency. To handle tie-breaking, push tuples like (freq, -num) or (-freq, num) appropriately.

After building the heap, extract elements and sort them by the required order (descending frequency, descending value).

Alternatively, you can get all (freq, num) pairs, sort by (-freq, -num), and take the first k—but that is O(n log n). The heap method is preferred.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.