vector<int> topKFrequent(vector<int>& nums, int k) {
The function `topKFrequent` takes a reference to a vector of integers `nums` and an integer `k`, and returns a vector of the `k` most frequent elements from `nums`.
2 : Map Declaration
map<int, int> ma;
Declare a map `ma` where the key is an integer from `nums` and the value is its frequency count.
3 : Loop Over Input
for(intx: nums)
Iterate over each element `x` in the input vector `nums`.
4 : Frequency Count
ma[x]++;
For each element `x`, increment its frequency count in the map `ma`.
5 : Priority Queue Declaration
priority_queue<pair<int, int>> pq;
Declare a priority queue `pq` of pairs where each pair consists of an integer (frequency) and an integer (element). This will be used to sort the elements by their frequencies.
6 : Map Iteration
for(auto [key, val]: ma)
Iterate through the map `ma`, where `key` is the element and `val` is its frequency.
7 : Push to Priority Queue
pq.push(make_pair(val, key));
Push each element-frequency pair to the priority queue. Elements with higher frequencies will be prioritized.
8 : Result Vector Declaration
vector<int> ans;
Declare an empty vector `ans` to store the top `k` frequent elements.
9 : While Loop
while(k--) {
The loop runs `k` times, extracting the top `k` frequent elements from the priority queue.
10 : Push Top Element to Result
ans.push_back(pq.top().second);
Push the element (second value of the top pair) from the priority queue to the result vector `ans`.
11 : Pop Top Element from Queue
pq.pop();
Remove the top element from the priority queue.
12 : Return Result
return ans;
Return the vector `ans` containing the `k` most frequent elements.
Best Case: O(n)
Average Case: O(n log k)
Worst Case: O(n log k)
Description: The time complexity is O(n) for counting the frequencies, and O(log k) for each insertion and extraction from the priority queue, resulting in a total time complexity of O(n log k).
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n) for storing the frequency count of each element in the map and the priority queue.
