Top K Frequent Elements - Leetcode Solution

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<int> topKFrequent(vector<int>& nums, int k) { // Create a hash map to store the frequency of each element in the array unordered_map<int, int> 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;
}

};

1