Top K Frequent Elements

Given an integer array nums and an integer k, return the k most frequent elements in the array. If there are multiple elements with the same frequency, return them in any order.

Example:

Input:

nums = [1, 1, 1, 2, 2, 3]
k = 2

Output:

[1, 2]

Explanation: In the input array, the element ‘1’ appears three times, and the element ‘2’ appears two times. The top 2 frequent elements are ‘1’ and ‘2’.

Solution in C++:

#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>

// Function to find the k most frequent elements in the array
std::vector<int> topKFrequent(std::vector<int>& nums, int k) {
    // Create a hash map to store the frequency count of each element
    std::unordered_map<int, int> freqMap;

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

    // Create a priority queue (min heap) to store the k most frequent elements
    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> pq;

    // Push elements and their frequencies into the priority queue
    for (auto it = freqMap.begin(); it != freqMap.end(); ++it) {
        pq.push(std::make_pair(it->second, it->first));

        // Keep the size of the priority queue at most k
        if (pq.size() > k) {
            pq.pop();
        }
    }

    // Extract the top k frequent elements from the priority queue
    std::vector<int> result;
    while (!pq.empty()) {
        result.push_back(pq.top().second);
        pq.pop();
    }

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

    return result;
}

int main() {
    std::vector<int> nums = {1, 1, 1, 2, 2, 3};
    int k = 2;

    std::vector<int> result = topKFrequent(nums, k);

    std::cout << "The top " << k << " frequent elements are: ";
    for (int num : result) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

Explanation:

1. The topKFrequent function takes a reference to a vector of integers nums and an integer k.
2. Inside the topKFrequent function, we create a freqMap using an unordered map (hash map) to store the frequency count of each element in the input array nums.
3. We create a priority queue (min heap) named pq to store the k most frequent elements. The priority queue will store pairs of elements and their frequencies, with the frequencies being used as the priority key.
4. We iterate through the freqMap and push each element-frequency pair into the priority queue. When the size of the priority queue exceeds k, we remove the smallest element (the one with the lowest frequency) from the queue using pq.pop().
5. After processing all elements, the priority queue will contain the k most frequent elements.
6. We extract the elements from the priority queue and store them in the result vector. Since the priority queue is a min heap, the elements with the highest frequency will be at the bottom of the queue. So, we reverse the result vector to get the elements in descending order of frequency.

Time Complexity:

The time complexity of this solution is O(n log k), where n is the number of elements in the input array nums. Building the frequency map takes O(n) time, and the priority queue operation of size k takes O(log k) time. In the worst case, where k is close to n, the time complexity approaches O(n log n).

Space Complexity:

The space complexity of this solution is O(n), where n is the number of elements in the input array nums. This is because we use an unordered map to store the frequency count, and a priority queue to store the top k frequent elements. In the worst case, where all elements have unique frequencies, the priority queue can hold up to n elements.