347. Top K Frequent Elements

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        """
        brote force 
        main idea: cnt dictionary + sort + slice 
        time O(NlgN) space O(N)
        """
        res = []
        ress = []
        d = {}
        for num in nums:
            if num not in d:
                d[num] = 1
            else:
                d[num] += 1
        for num, fre in d.items():
            res.append([num,fre])
        res.sort(key = lambda k: k[1],reverse = True)
        for i in range(k):
            ress.append(res[i][0])
        return ress

from collections import Counter
import heapq
class Solution:
    """
    main idea: Heap + Counter
    time O(NlgK) space O(N)
    """"
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        # edge case k == len
        if not nums or len(nums)==k:
            return nums
        #step1: cnt freq
        cnt = Counter(nums)
        # step2: max heap, keep heap full throughout full iteration
        max_h = [(-freq,val) for val,freq in cnt.items()]
        heapq.heapify(max_h) # don't for get to heapify
        # build res 
        res = []
        for i in range(k):
            res.append(heapq.heappop(max_h)[1])
        return res 

from collections import Counter
import heapq
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        # edge case k == len
        if not nums or len(nums)==k:
            return nums
        #step1: frequency bucket wit sublist 
        b = [[] for _ in range(len(nums)+1)] 
        #step2: Counter
        cnt = collections.Counter(nums)
        #step3: assign each val into bucket 
        for val,freq in cnt.items():
            b[freq].append(val)
        # step4: flatlist 
        flat_li = [x for subli in b for x in subli]
        # step5: reverse iterate flat_li and get last k
        return flat_li[::-1][:k]