Top K Frequent Elements medium

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]

Steps

1. Frequency Counting: Count the frequency of each element in the input array nums. We can use a map (or unordered_map for faster average-case lookup) to store the element as the key and its frequency as the value.

2. Priority Queue (Min-Heap): Create a min-heap priority queue. We'll use a custom comparator to prioritize elements based on their frequency (elements with lower frequency will have higher priority). The heap will store pairs of (frequency, element).

3. Populate the Heap: Iterate through the frequency map. For each element and its frequency, add the pair (frequency, element) to the min-heap. Because it's a min-heap, only the k elements with the highest frequencies will remain in the heap once its size exceeds k.

4. Extract Top K: Extract the top k elements from the min-heap. These are the k most frequent elements.

Explanation

The min-heap is crucial for efficiency. As we iterate through the frequency map, if the heap size exceeds k, the element with the lowest frequency (the top of the min-heap) is automatically removed, ensuring that we only keep track of the k most frequent elements encountered so far. This avoids unnecessary storage and processing of less frequent elements.

Code

#include <iostream>
#include <vector>
#include <map>
#include <queue>

using namespace std;

vector<int> topKFrequent(vector<int>& nums, int k) {
    map<int, int> freqMap; //Store element and its frequency

    //Count frequency of each element
    for (int num : nums) {
        freqMap[num]++;
    }

    //Min-heap to store (frequency, element) pairs.
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> minHeap;

    //Populate the min-heap
    for (auto const& [element, frequency] : freqMap) {
        minHeap.push({frequency, element});
        if (minHeap.size() > k) {
            minHeap.pop(); //Remove the element with lowest frequency if size exceeds k
        }
    }


    //Extract top k elements
    vector<int> topK;
    while (!minHeap.empty()) {
        topK.push_back(minHeap.top().second);
        minHeap.pop();
    }
    //Reverse the vector to maintain order from most to least frequent
    reverse(topK.begin(), topK.end());
    return topK;
}

int main() {
    vector<int> nums = {1, 1, 1, 2, 2, 3};
    int k = 2;
    vector<int> result = topKFrequent(nums, k);
    cout << "Top " << k << " frequent elements: ";
    for (int num : result) {
        cout << num << " ";
    }
    cout << endl;
    return 0;
}

Complexity

• Time Complexity: O(N log k), where N is the number of elements in nums. Building the frequency map takes O(N) time. The heap operations (insertion and deletion) take O(log k) time each, and we perform at most N heap operations.

• Space Complexity: O(N) in the worst case (if all elements are unique), primarily due to the frequency map. The heap's space complexity is O(k).