Last updated on February 20th, 2025 at 10:01 am

Here, we see a Top K Frequent Elements LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Hash Table, Heap

Companies

Pocketgems, Yelp

Level of Question

Medium

Top K Frequent Elements LeetCode Solution

1. Problem Statement

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]

2. Coding Pattern Used in Solution

The coding pattern used in all the provided implementations is “Top ‘K’ Elements”. This pattern is commonly used when we need to find the top K frequent, smallest, or largest elements in a dataset. The problem involves using data structures like heaps, hash maps, or buckets to efficiently extract the desired elements.

3. Code Implementation in Different Languages

3.1 Top K Frequent Elements C++

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,int> map;
        for(int num : nums){
            map[num]++;
        }
        vector<int> res;
        priority_queue<pair<int,int>> pq; 
        for(auto it = map.begin(); it != map.end(); it++){
            pq.push(make_pair(it->second, it->first));
            if(pq.size() > (int)map.size() - k){
                res.push_back(pq.top().second);
                pq.pop();
            }
        }
        return res;
    }
};

3.2 Top K Frequent Elements Java

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
	    List<Integer>[] freqSorted = new List[nums.length +1];
	    Map<Integer, Integer> frequencyMap = new HashMap();
	    List<Integer> res = new ArrayList();
	    for(int n: nums)
		    frequencyMap.put(n, frequencyMap.getOrDefault(n, 0) + 1);
        for(int key: frequencyMap.keySet()){
	        if(freqSorted[frequencyMap.get(key)] == null)
		        freqSorted[frequencyMap.get(key)] = new ArrayList();
	        freqSorted[frequencyMap.get(key)].add(key);
        }
        for(int i = freqSorted.length - 1; i >= 0 && res.size() < k; i--)
	        if(freqSorted[i] != null){
			    res.addAll(freqSorted[i]);
        }
    return res.stream().mapToInt(i->i).toArray();
    }
}

3.3 Top K Frequent Elements JavaScript

var topKFrequent = function(nums, k) {
    const freqMap = new Map();
    const bucket = [];
    const result = [];
    for(let num of nums) {
        freqMap.set(num, (freqMap.get(num) || 0) + 1);
    }
    for(let [num, freq] of freqMap) {
        bucket[freq] = (bucket[freq] || new Set()).add(num);
    }
    for(let i = bucket.length-1; i >= 0; i--) {
        if(bucket[i]) result.push(...bucket[i]);
        if(result.length === k) break;
    }
    return result;
};

3.4 Top K Frequent Elements Python

class Solution(object):
    def topKFrequent(self, nums, k):
        map=Counter(nums)
        result=[]
        for key,value in map.items():
            result.append([key,value])
        result.sort(key=lambda x:x[1],reverse=True)
        return [x[0] for x in result[:k]]

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(n + m log m)	O(n + m)
Java	O(n + m)	O(n + m)
JavaScript	O(n + m)	O(n + m)
Python	O(n + m log m)	O(n + m)

here,

• n: Total number of elements in the input array nums.
• m: Number of unique elements in the input array nums.
• O(n) for frequency map
• O(m) for bucket traversal 
• O(m log m) for heap operations

• The C++ implementation uses a heap, which is more suitable for scenarios where k is much smaller than the total number of unique elements (m).
• The Java and JavaScript implementations use a bucket sort approach, which is more efficient when k is close to m.
• The Python implementation uses sorting, which is simple but less efficient compared to the bucket sort approach for large datasets.