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; } }