deepSWE.io

Top K Frequent Elements

HeapHashing

15 min

Problem Statement

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

Example

Example 1:

Input: nums = [1,1,1,2,2,3], k = 2

Output: [1,2]

Constraints

1 ≤ nums.length ≤ 10^5
k is in the range [1, the number of unique elements in the array].
It is guaranteed that the answer is unique.

Solution (Hash Map + Min-Heap)

This problem can be solved efficiently by combining a hash map and a min-heap. First, we use a hash map to count the frequency of each element in the input array. Then, we use a min-heap of size k to keep track of the k most frequent elements encountered so far.

Algorithm Steps

Build a hash map to store the frequency of each number.
Create a min-heap. Iterate through the numbers in the frequency map.
Push elements into the heap. If the heap size exceeds k, pop the element with the smallest frequency.
The elements remaining in the heap are the top k frequent elements.

Input Array

Frequency Map

Min-Heap (size k=2)

Start: Build a frequency map.

Top K Frequent Elements Solution


import heapq
from collections import Counter

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        freqs = Counter(nums)
        heap = []
        
        for num, freq in freqs.items():
            heapq.heappush(heap, (freq, num))
            if len(heap) > k:
                heapq.heappop(heap)
                
        return [num for freq, num in heap]