347. Top K Frequent Elements

347. Top K Frequent Elements

Summary

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Approach

Use a frequency counter and a min-heap.

We count the frequency of each number with a hash map. Then we keep only the k most frequent numbers in the min-heap.

Function

Initialization:

• counter
• minheap

For each number n in nums: counter[n] += 1

For each number, count in counter.items(): if len(minheap) < k: heappush(minheap, (count, number)) else: if count > minheap[0][0]: heapreplace(minheap, (count, number))

Return [item[1] for item in minheap].

Complexity

Time Complexity: O(N log K). First, we build the counter in O(N). Then we process the heap in O(N log K). Finally, extracting the answer takes O(K). Space Complexity: O(N + K).