Top K Frequent Elements

Question (LC.347)

Given a list of integers, return the top k most frequent values.

Example

I: [1, 1, 1, 2, 2, 3], k = 2 
O: [1, 2] 

I: [3, 2, 1], k = 1 
O: the answer is not unique 

Simple Heap

def topKFrequent(self, nums: List[int], k: int) -> List[int]:

    # use a hash map to reduce this problem to a common top k problem

    if len(nums) == 0 or k == 0:
        return []

    num_dict: Dict[int, int] = {}

    for num in nums:
        if num in num_dict:
            num_dict[num] = num_dict[num] + 1
        else:
            num_dict[num] = 1

    # use a min heap of k elements

    min_heap = []

    for key in num_dict:
        if len(min_heap) < k:
            heapq.heappush(min_heap, (num_dict[key], key))
        elif num_dict[key] > min_heap[0][0]:
            heapq.heappop(min_heap)
            heapq.heappush(min_heap, (num_dict[key], key))

    return [k for (v, k) in min_heap]

Worst case O(nlogk) time and O(n) + O(k) space

Quick Select

Bucket Sort