Big O Practice: Top K Frequent

import heapq
from collections import Counter

def top_k_frequent(nums, k):
    counts = Counter(nums)
    heap = []
    for num, freq in counts.items():
        heapq.heappush(heap, (freq, num))
        if len(heap) > k:
            heapq.heappop(heap)
    return [num for _, num in heap]

Variables

• n - length of the input array nums
• k - number of top-frequency elements to return

Explanation

Counting all numbers is **O(n)**; pushing each of the up-to-`n` distinct counts into a size-`k` heap costs **O(log k)** per push, total **O(n log k)**. The counts map holds up to `n` distinct values; the heap holds `k` - total space **O(n + k)**.

More Big O practice problems · Today's daily problem