Top K Frquent Elements

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:

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

Intuition:

1. Using Max Heap wrt to the number of occurrences (cnt) of the elements.
2. Using Bucket Sort wrt to the number of occurrences (cnt) of the elements.
   Basic idea is have a array of len(nums) + 1 where each index will denotes cnt and then append the element to that index whose occurrence is that index. Then iterate over that array in reverse till you get k elements.

Code:

My Solution

def topKFrequent(self, nums: List[int], k: int) -> List[int]:
	cnt = Counter(nums)  # O(n)
	cnt_arr = [(val, key) for key, val in cnt.items()] # O(n)
	cnt_arr.sort(reverse=True)
	ans = [key for key,_ in cnt_arr]
	return ans

Here Time Complexity is O(nlogn)

Max Heap

def topKFrequent(self, nums: List[int], k: int) -> List[int]:
	cnt = Counter(nums)
	cnt_arr = [(val, key) for key, val in cnt.items()] # O(n)
	heapq.heapify_max(cnt_arr) # O(n)
	ans = [heappop_max(cnt_arr)[1] for _ in range(k)] # O(klogn)
	return ans

Here Time Complexity is O(klogn)

Using Bucket Sort

def topKFrequent(self, nums: List[int], k: int) -> List[int]:
	cnt = Counter(nums)
	# using set so that no duplicated values while add to the bkt
	bkt = [set() for _ in range(len(nums) + 1)]
	for num in nums:
		bkt[cnt[num]].add(num)
	ans = []
	for arr in bkt:
		if k and arr:
			ans += arr
			k -= len(arr)
		if k <= 0:
			break
	return ans

Here Time Complexity is O(n)

#max-heap #heap #bucket-sort