Top K Frequent Elements LeetCode Solution

Table of Contents

Problem Statement

Top K Frequent Elements LeetCode Solution Says that – Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Example 1:

Input:

 nums = [1,1,1,2,2,3], k = 2

Output:

 [1,2]

Example 2:

Input:

 nums = [1], k = 1

Output:

[1]

Constraints:

1 <= nums.length <= 10⁵
k is in the range [1, the number of unique elements in the array].
It is guaranteed that the answer is unique.

Algorithm:

Idea:

In order to find the Top k Frequent Elements. First, we will focus on the frequency of each element present in an array.
After finding the Frequency of Each element we will make one maximum heap and push all elements into the heap with their Frequency.
At last, we will make one result list and will pop out the k element from the heap and append that element into the result and return the result.

Approach:

At first, We will make one Hashmap and will traverse through the whole array and set the frequency of each element as value and element as Key in the Hashmap.
After that, we will make one priority queue(maxheap) and again traverse through the whole array and push all the elements as tuple pairs (-value, key) into the maxheap.
Then, we will run a loop from 0 to K and pop out the elements from maxheap and append the Key of each tuple into the result and return the result.
Hence We will find the Top K frequent Elements.

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        dic = {}
        
        for i in nums:
            if i in dic:
                dic[i] += 1
                
            else:
                dic[i] = 1
        
        max_heap = []
        for i in dic:
            heapq.heappush(max_heap,(-dic[i],i))
            
        result = []
        for i in range(k):
            result.append(heapq.heappop(max_heap)[1])
        
        return result

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        
      Map<Integer, Integer> dic = new HashMap<>();
        for(int num : nums){ dic.put(num, dic.getOrDefault(num, 0) + 1); }
        
        Queue<Integer> max_heap = new PriorityQueue<>((a, b) -> dic.get(b) - dic.get(a));
        for(int key : dic.keySet()){ max_heap.add(key); }
        
        int[] result = new int[k];
        for(int i = 0; i < k; i++){
            result[i] = max_heap.poll();
        }
        
        return result;
    } 
}

Complexity Analysis of Top K Frequent Elements Leetcode Solution:

Time complexity:

The Time Complexity of the above solution is O(nlogn) where n = the size of the input array. We have traversed the entire array and for each element, we are doing the heapify operation.

Space complexity:

The Space Complexity of the above solution is O(n) since we are creating a max heap of size n.

https://leetcode.com/problems/kth-largest-element-in-an-array/