LeetCode 347: Top K Frequent Elements — Step-by-Step Visual Trace

#python #algorithms #leetcode

Medium — Hash Table | Heap | Priority Queue | Frequency Counting

The Problem

Given an array of integers and a number k, return the k most frequently occurring elements in the array.

Approach

Build a frequency map of all elements, then use a min-heap of size k to track the k most frequent elements. For each element, push it to the heap and pop the least frequent if heap size exceeds k.

Time: O(n log k) · Space: O(n)

Code

import heapq

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        frequency_map = {}
        for num in nums:
            frequency_map[num] = frequency_map.get(num, 0) + 1

        min_heap = []
        for num, frequency in frequency_map.items():
            heapq.heappush(min_heap, (frequency, num))
            if len(min_heap) > k:
                heapq.heappop(min_heap)

        return [num for frequency, num in min_heap]