347. Top K Frequent Elements

Approach: Min-Heap

Algorithm:

1. Count the frequency of each element in the array.
2. Use a min-heap to keep track of the k most frequent elements.
3. Iterate through the frequency map and add elements to the heap, maintaining its size at k.
4. Return the elements in the heap.

from collections import Counter
import heapq

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        count = Counter(nums)

        heap = []
        for num, freq in count.items():
            heapq.heappush(heap, (freq, num))
            if len(heap) > k:
                heapq.heappop(heap)

        return [num for _, num in heap]

• Time: $O(n \log k)$ — where $n$ is the number of elements in the array, and we perform at most $n$ heap operations, each taking $O(\log k)$ time.
• Space: $O(n + k)$ — the frequency map holds up to $n$ entries and the heap holds up to $k$ elements.

Last updated on