347. Top K Frequent Elements

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

Example

---

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

💻 Code

Approach : Count each number using hash, then prioritize for k number of elements.

1. Brute force

---

• Hash Map & Priority Queue
• TC : O(n log n)
  • n : hash map
  • log m : heap
• SC: O(n)

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        freq = {}

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

        heap = []
        for num, count in freq.items():
            heapq.heappush(heap, (count, num))  # store count first! (minHeap)
            if len(heap) > k:
                heapq.heappop(heap)
        
        res = [num for count, num in heap]

        return res

This method is operated in 2 steps.

1. First, it counts with a hash map so that we know each element appeared how many times.
   
2. Second, a priority queue can be used by importing heapq. Since the minheap is a default implementation in Python, storing count first allows it to pop least frequent elements first when heapq is full; this only stores k number of most frequent elements.

2. Optimised Solution

---

• Hash Map & Bucket Sort
• TC : O(n)
• SC: O(n)

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        res = []
        freq = {}
        # [[], [], [], [], [], []]
        buckets = [[] for _ in range(len(nums))]
        
        for num in nums:
            if num not in freq:
                freq[num] = 1
            else:
                freq[num] += 1

        for num, cnt in freq.items():
            # bucket starts from index 0, so cnt - 1
            buckets[cnt - 1].append(num)
        
        # iterate the bucket from the end (most frequent)
        for i in range(len(buckets) - 1, -1, -1):
            if buckets[i]:
                for j in bucekts[i]:
                    res.append(j)
                    if len(res) == k:
                        return res

The feature of the Bucket Sort is to store multiple elements at a single index by creating subarrays.

We can simply iterate the bucket from the back until we have k number of elements.

Additional Material

Using extend(arr) helps to have more brief code.

# Learning how to use extend() function
# it stores all elements inside the bracket (no bracket included)
    for i in range(len(buckets) - 1, -1, -1):
        if buckets[i]:
            res.extend(buckets[i])
            if len(res) >= k:   # extend could store more than k
                return res[:k]

extend(arr) basically stores all elements in a single bucekt.