#347. Top K Frequent Elements | LeetCode Python Solution

Problem

LeetCode Problem

347. Top K Frequent Elements

Python Solution

class Solution(object):
    def topKFrequent(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        topKNums = []

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

        # Store the frequency of each number in a dictionary
        # In our example, our dictionary would look like {1:3, 2:2, 3:1, 4:2}
        freq = {}
        for n in nums:
          freq[n] = freq.get(n, 0) + 1

        # Create a multi-storage bucket with the length of the integer array nums + 1 as its size.
        # Note that there might be more than one numbers with the same frequency.
        # We use list to store more than one elements at the same level.
        bucket = []
        for _ in range(len(nums)+1):
          bucket.append([])

        # Based on frequency of the number, put it in the appropriate bucket level.
        # In our example, put 1 at level 3, put 2 and 4 at level 2 and put 3 at level 1.
        for num, count in freq.items():
          bucket[count].append(num)

        # Loop over the bucket elements in the reverse order
        # Collect top K frequent numbers and return when the size of topKNums list match with the input value k.
        for idx in range(len(bucket)-1, 0, -1):
          nums = bucket[idx]
          for num in nums:
            topKNums.append(num)
            if len(topKNums) == k:
              return topKNums