LeetCode #347: Top K Frequent Elements

LeetCode Solutions

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

The brute force approach to solving this problem would be to count the frequency of each element in the given array and then sort the elements based on their frequency. Finally, we can return the top k frequent elements. However, this would take O(n log n) time complexity. A more efficient approach is to use a hash table to store the frequency of each element and a min heap to store the top k frequent elements.

Steps to solve the problem:

  1. Create an empty dictionary to store the frequency of each element in the given array.
  2. Iterate through the given array and count the frequency of each element. Add each element and its frequency to the dictionary.
  3. Create an empty min heap to store the top k frequent elements. We will use a min heap because we want to keep track of the minimum frequent element in the heap.
  4. Iterate through the dictionary and add each element and its frequency to the min heap. If the size of the heap exceeds k, we pop the minimum frequent element from the heap.
  5. Finally, return the elements from the heap.

Python Code: Here’s the Python code to solve the Top K Frequent Elements problem using the hash table and min heap approach:

import heapq

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        # Create an empty dictionary to store the frequency of each element
        freq_dict = {}
        
        # Iterate through the given array and count the frequency of each element
        for num in nums:
            if num in freq_dict:
                freq_dict[num] += 1
            else:
                freq_dict[num] = 1
        
        # Create an empty min heap to store the top k frequent elements
        heap = []
        
        # Iterate through the dictionary and add each element and its frequency to the min heap
        for key, val in freq_dict.items():
            heapq.heappush(heap, (val, key))
            if len(heap) > k:
                heapq.heappop(heap)
        
        # Return the elements from the heap
        return [element[1] for element in heap]

Runtime and Space Complexity

The runtime complexity of the hash table and min heap approach is O(n log k), where n is the number of elements in the given array and k is the given value of k. This is because we are iterating through the given array to count the frequency of each element, and we are adding and removing elements from the heap, which takes O(log k) time.

The space complexity of the solution is O(n + k), as we are storing the frequency of each element in the dictionary and the top k frequent elements in the heap.