0347. Top K Frequent Elements

Problem Category:: Hash table, Heap, Quick select Neetcode Category:: Arrays and Hashing

https://leetcode.com/problems/top-k-frequent-elements/description/

Given an integer array nums and an integer k, return the k most frequent elements.

• You may return the answer in any order
• It is guaranteed that the answer is unique
• Aim for better than $O(nlog(n))$

Method 1: Heap

TBC

Method 2: Quickselect

TBC

Method 3: Hash tables + buckets

$O(n)$ average case method (using Hash table), approximating the approach of a Bucket sort

Python implementations

Full length

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        buckets = [[] for num in nums] #create len(nums) buckets
        # Equiv: ctr = collections.Counter(nums), call .items()
        ctr = {}
        for num in nums:
            if num not in ctr:
                ctr[num] = 1
            else:
                ctr[num] += 1
 
        for num, freq in ctr.items():
            buckets[-freq].append(num)
        
        arr = []
        for bucket in buckets:
            arr.extend(bucket)
        #equiv: list(itertools.chain(*buckets))
 
        return arr[:k]
        #equiv: return list(itertools.chain(*buckets))[:k]

Pythonic

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        buckets = [[] for num in nums] #create len(nums) buckets
 
        for num, freq in collections.Counter(nums).items(): #dict
            buckets[-freq].append(num)
        
        return list(itertools.chain(*buckets))[:k]

---

• task Add heap/quickselect methods