# Solution For Top K Frequent Elements

Problem Statement:

Given a non-empty array of integers, return the k most frequent elements.

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:

• You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
• Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.
• It’s guaranteed that the answer is unique, in other words the set of the top k frequent elements is unique.
• You can return the answer in any order.

Solution:

The goal of this problem is to find the k most frequent elements from an array of integers. We can use a hash map to store the frequency of each element in the array. We can then use a priority queue (min heap) to keep track of the k most frequent elements.

We can first create a hash map to store the frequency of each element in the array. Then, we can iterate through the hash map and create a pair of each element and its frequency. We can then push this pair into a priority queue.

Since we want the k most frequent elements, we only need to keep k elements in the priority queue. If the size of the priority queue exceeds k, we can remove the least frequent element from the queue. Finally, we can return the k elements from the priority queue.

Algorithm:

1. Create a hash map to store the frequency of each element in the array.
2. Create a priority queue (min heap) to keep track of the k most frequent elements.
3. Iterate through the hash map and create a pair of each element and its frequency. Push this pair into the priority queue.
4. If the size of the priority queue exceeds k, remove the least frequent element from the queue.
5. Return the k elements from the priority queue.

Code:

class Solution {
public:
vector topKFrequent(vector& nums, int k) {
// Create a hash map to store the frequency of each element in the array
unordered_map freq_map;
for (int num : nums) {
freq_map[num]++;
}

``````    // Create a priority queue (min heap) to keep track of the k most frequent elements
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
for (auto it = freq_map.begin(); it != freq_map.end(); it++) {
// Create a pair of each element and its frequency, and push it into the priority queue
pq.push(make_pair(it->second, it->first));

// If the size of the priority queue exceeds k, remove the least frequent element from the queue
if (pq.size() > k) {
pq.pop();
}
}

// Create a vector to store the k most frequent elements
vector<int> result;
while (!pq.empty()) {
result.push_back(pq.top().second);
pq.pop();
}

// Reverse the result vector to get the elements in descending order of frequency
reverse(result.begin(), result.end());

return result;
}
``````

};

## Step by Step Implementation For Top K Frequent Elements

```import java.util.*;

class Solution {

// Function to find the k most frequent elements

static List topKFrequent(int[] nums, int k)

{

// Create a HashMap with key as

// the element and value as its

// frequency in the given array

HashMap

freq = new HashMap<>();

for (int i = 0; i < nums.length; i++)

{

// If this is the first occurrence

// of the element

if (!freq.containsKey(nums[i]))

freq.put(nums[i], 1);

// If elements already exists in

// the map, increment its value

else

freq.put(nums[i],freq.get(nums[i])+1);

}

// Create a min heap

PriorityQueue >

pq = new PriorityQueue<>

(freq.size(), new Comparator >()

{

@Override public int

compare(Map.Entry e1,

Map.Entry e2)

{

return e1.getValue() - e2.getValue();

}

});

// Add all elements of the map to the min heap

for (Map.Entry entry :

freq.entrySet())

{

pq.add(entry);

}

// Remove all elements from the heap

// till only k elements are left

while (pq.size() > k)

{

pq.poll();

}

// Create a list from the remaining

// k elements

List res = new LinkedList<>();

while (!pq.isEmpty())

{

res.add(pq.poll().getKey());

}

return res;

}

}```
```from collections import Counter

class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
# Use Counter to count the frequency of each element
count = Counter(nums)

# Get a list of tuples (element, frequency) sorted in descending order
# by frequency
freq_tuples = count.most_common()

# Initialize an empty list to store the top k frequent elements
top_k = []

# Iterate over the first k tuples and append the element to the list
for i in range(k):
top_k.append(freq_tuples[i][0])

return top_k```
```var topKFrequent = function(nums, k) {
// create a map to store the frequency of each element
const map = new Map();
for (let num of nums) {
if (map.has(num)) {
map.set(num, map.get(num) + 1);
} else {
map.set(num, 1);
}
}

// create an array of [num, frequency] pairs
const pairs = [];
for (let [num, freq] of map) {
pairs.push([num, freq]);
}

// sort the pairs by frequency
pairs.sort((a, b) => a[1] - b[1]);

// return the last k pairs
const result = [];
for (let i = pairs.length - 1; i >= pairs.length - k; i--) {
result.push(pairs[i][0]);
}
return result;
};```
```vector topKFrequent(vector& nums, int k) {
// create an unordered_map with key as number and value as its frequency
unordered_map hash;
for (auto i : nums)
hash[i]++;

// create a min heap
priority_queue, vector>, greater>> pq;

// push all the elements of hash into the min heap
for (auto it : hash)
pq.push({ it.second, it.first });

// pop from the min heap exactly k times and print those k elements
vector res;
for (int i = 0; i < k; i++) {
res.push_back(pq.top().second);
pq.pop();
}
return res;
}```
`public IList TopKFrequent(int[] nums, int k) { // create a map of numbers to frequencies var map = new Dictionary(); foreach (var n in nums) { if (map.ContainsKey(n)) { map[n]++; } else { map[n] = 1; } } // create a min heap to track the top k frequent elements var heap = new MinHeap(k); foreach (var key in map.Keys) { heap.Add(key, map[key]); } // return the top k frequent elements return heap.GetElements(); } public class MinHeap { private List> _elements; public MinHeap(int capacity) { _elements = new List>(capacity); } public void Add(int key, int value) { if (_elements.Count == 0) { _elements.Add(new KeyValuePair(key, value)); return; } // find the index to insert the new element int index = _elements.Count; _elements.Add(new KeyValuePair(key, value)); // heapify up while (index > 0) { int parentIndex = (index - 1) / 2; if (_elements[index].Value >= _elements[parentIndex].Value) { break; } Swap(index, parentIndex); index = parentIndex; } } public IList GetElements() { return _elements.Select(e => e.Key).ToList(); } private void Swap(int index1, int index2) { var temp = _elements[index1]; _elements[index1] = _elements[index2]; _elements[index2] = temp; } }`
Scroll to Top

## Top 100 Leetcode Practice Problems In Java

Get 30% Off Instantly!
[gravityforms id="5" description="false" titla="false" ajax="true"]