Top K Frequent Elements

LeetCode #347 [Medium]

Problem Statement

Given an array of integers, return the k most frequent elements.

Example: nums = [1,1,1,2,2,3], k=2 → Output: [1,2]

Approach 1: Hash Map + Sorting

Explanation: Count frequencies and sort by frequency.

Time Complexity: O(n log n)

Space Complexity: O(n)

freq = hashmap()
for num in nums:
    freq[num] += 1
sort freq by values descending
return first k elements
Heap Sort Flowchart

💡 Think: Count with a map, then sort by frequency and take the top k.

Approach 2: Min Heap (Optimal)

Explanation: Maintain min-heap of size k for frequencies.

Time Complexity: O(n log k)

Space Complexity: O(k)

freq = hashmap()
for num in nums:
    freq[num] += 1
create min-heap
for num, count in freq:
    push (count,num)
    if heap size > k:
        pop min
return all elements in heap
Heap Sort Flowchart

💡 Think: Maintain a size-k min-heap keyed by counts to keep only the most frequent.

Solve on LeetCode