0347.Top K Frequent Elements

• Link: 347.Top K Frequent Elements - Medium
• Track: NeetCode150

Question

Example 1:

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

Restate the problem

• Given an array of nums and an integer k
• Return the k most frequency elements
• Constraints:
  • Assume the answer is unique

Edge Case

• nums = [1,1,1], k = 1 → return [1]
• Negative numbers, nums = [-1,-1,0,0,0], k = 1 → return [0]
• [], k = 2 → return []

---

Method	Approach	Time Complexity	Space Complexity
Method 1 ⭐	Bucket Sort	$O(n)$	$O(n)$
Method 2 ⭐	Heap	$O(n+mlogk)$	$O(m+k)$
Method 3	Counter + Sort	$O(n+mlogm)$	$O(m)$

Method 1 - Bucker Sort

• Why Bucket Sort works?
  • Bucket sort works when the key in a small integer range. 1....n, bounded integer range

Approach

• Use Counter to build {num: freq}
• Create buckets, bucket[freq]stores all numbers with that frequency
• Scan bucket from n down to 1
  • collect numbers until we have k

Complexity

• Time Complexity: $O(n)$
  • Scan take $O(m+n)$, m ≤ n, so O(n+m)=O(n)
• Space Complexity: $O(n)$

Code

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        counter = Counter(nums) # {num: freq} O(n)
        
        bucket = [[] for _ in range(n + 1)]
        for num, freq in counter.items():
            bucket[freq].append(num)
        
        res = []
        for idx in range(len(bucket) - 1, -1, -1): # O(n)
            for num in bucket[idx]:                # O(m)
                res.append(num)
	            if len(res) == k:
	                return res
		return res

Method 2 - Heap

Approach

• Use Counter to build {num: freq}
• Maintain a min-heap of size at most k
• For each num in Counter:
  • heap push
  • if heap size > k, heappop to remove the smallest frequency
• Return the remaining in the heap

Complexity

• Time Complexity: $O(n+mlogk)$
  • m = the number of unique num
  • k = the number of elements need to return
• Space Complexity: $O(m+k)$
  • worst case: $O(n)$

Code

from collections import Counter
import heapq
 
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        counter = Counter(nums) # O(n)
 
        heap = []
        for num, freq in counter.items(): # O(m)
            heapq.heappush(heap, (freq, num)) # O(logk)
            if len(heap) > k:
                heapq.heappop(heap)
        
        return [num for freq, num in heap]

Method 2 - Counter + Sort

Complexity

• Time Complexity: $O(n+mlogm)$
  • n = len(nums)
  • m = the number of unique num
• Space Complexity: $O(m)$

Code

from collections import Counter
import heapq
 
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        counter = Counter(nums) # O(n)
 
        freqs = [(freq, num)for num, freq in counter.items()] # O(m)
        freqs.sort(reverse=True) # O(mlogm)
        
        return [num for _, num in freqs[:k]] # O(k)

---

Common mistake