Top K Frequent Elements

?? Problem Overview:

Given an integer array nums, return the k most frequent elements. This is a common interview problem that can be solved efficiently using three distinct approaches: Sorting, Heap, and Bucket Sort.

1?? Sorting Approach

Solution:

• First, count the frequency of each number using a dictionary.
• Sort the dictionary by frequency in descending order.
• Extract the top k frequent elements.

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        count = {}
        for num in nums:
            count[num] = 1 + count.get(num, 0)

        arr = []
        for num, cnt in count.items():
            arr.append([cnt, num])
        arr.sort()  # Sorting the array based on frequency

        res = []
        while len(res) < k:
            res.append(arr.pop()[1])
        return res
        

?? Time Complexity: O(n log n)

?? Space Complexity: O(n) Where n is the length of the array.

2?? Heap Approach

Solution:

• Count the frequency of elements.
• Use a min-heap to store the k most frequent elements.
• If the heap exceeds size k, remove the least frequent element.

import heapq

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        count = {}
        for num in nums:
            count[num] = 1 + count.get(num, 0)

        heap = []
        for num in count.keys():
            heapq.heappush(heap, (count[num], num))  # Push frequency and element
            if len(heap) > k:  # Remove least frequent element if size exceeds k
                heapq.heappop(heap)

        res = []
        for i in range(k):
            res.append(heapq.heappop(heap)[1])
        return res
        

?? Time Complexity: O(n log k)

?? Space Complexity: O(n + k) Where n is the length of the array, and k is the number of top frequent elements.

3?? Bucket Sort Approach

Solution:

• Count the frequency of each number.
• Create buckets where each index holds numbers with the same frequency.
• Traverse the buckets in reverse order to get the most frequent elements.

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        count = {}
        freq = [[] for i in range(len(nums) + 1)]  # Frequency bucket array

        for num in nums:
            count[num] = 1 + count.get(num, 0)

        for num, cnt in count.items():
            freq[cnt].append(num)  # Bucket elements by frequency
        
        res = []
        for i in range(len(freq) - 1, 0, -1):  # Iterate from highest to lowest frequency
            for num in freq[i]:
                res.append(num)
                if len(res) == k:
                    return res
        

?? Time Complexity: O(n)

?? Space Complexity: O(n) Where n is the length of the array.

Conclusion:

Which approach is best for you?

• Sorting is the most straightforward but can be inefficient for large arrays.
• Heap is optimal when k is much smaller than n.
• Bucket Sort is the most efficient for this problem, as it runs in O(n) time.

?? Time and Space Complexity Recap:

Approach Time Complexity Space Complexity Sorting O(n log n) O(n) Heap O(n log k) O(n + k) Bucket Sort O(n) O(n)

?? Which method do you prefer? Let me know in the comments below or feel free to share your thoughts!

#LeetCode #Python #Algorithms #DataStructures #InterviewPrep #CodingChallenge #TechInterview #ProblemSolving #BucketSort #Heap