Top K Frequent Elements

Problem Summary

(Write in your own words, not copied from LeetCode. This forces comprehension.)

• Given an Array return k most frequent elements

Key Observations

(Patterns, constraints, or hints in the problem statement.)

• Can use a variation of Bucket Sort for the most optimized solution

Approach Taken

(Step-by-step logic or pseudocode before coding.)

• Use Hash Map to count how many values exist
• Initialize an Array with $n+1$ empty lists - these will be our buckets
• For each value in our Hash Map put it in our bucket based on their count

Why This Works

(Explain the core reason the solution is correct.)

• If we have $n$ values then at most we can have $n$ times a single value
• This means at most we can have $n$ buckets to put values into

Main Concepts Used

(Mark the CS concepts or algorithms used.)

• Hash Map
• Array
• Bucket Sort

Time & Space Complexity

• Time: $O(n)$ → Reason: We loop through all the values once or twice
• Space: $O(n)$ → Reason: We store 2x values at most

Code

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        # create dict of num to count O(n)
        # heapify dict items O(n)
        # get k items O(k * log n)
        # final time complexity O(n + k log n)??
        hashMap = {}

        for num in nums:
            hashMap[num] = hashMap.get(num, 0) + 1
        
        listOfKeyValues = []
        for key, value in hashMap.items():
            listOfKeyValues.append((-1 * value, key))
        
        heapq.heapify(listOfKeyValues)

        result = []
        for _ in range(k):
            val = heapq.heappop(listOfKeyValues)[1]
            result.append(val)
        return result

Optimized Solution

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

        for num in nums:
            hashMap[num] = hashMap.get(num, 0) + 1
        
        buckets = [[] for x in range(len(nums) + 1)]

        for key, value in hashMap.items():
            buckets[value].append(key)

        result = []
        for i in range(len(buckets) - 1, 0, -1):
            for num in buckets[i]:
                result.append(num)
                if len(result) == k:
                    return result

Common Mistakes / Things I Got Stuck On

• How to do max heap
• Not to negate the key that does not have to be negated
• Creating buckets has to be done in a loop
  • buckets = [[] for x in range(len(nums) + 1)]
  • CANNOT do [] * len(nums) + 1 because it will put the same reference to that list $n+1$ times