/*
   Leet Code 347. Top K Frequent Elements

   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]
  
   Example 3:
     Input: nums = [1,2,1,2,1,2,3,1,3,2], k = 2
     Output: [1,2]
  
   algorithm's time complexity must be better than O(n log n), where n is the
   array's size.

   We need to return the k most frequent elements in any order. If there are
   ties in frequency, any of the tied elements is acceptable.”

   First I count frequencies using a hash map → O(n) time, O(n) space.

   Then I have two good options:
     - Build a max-heap of size ≈ number of unique elements and extract k times
           → O(n + m log m) where m ≤ n is number of unique elements
  
     - use a min-heap of size k (better when k << n)
     
   Today I’ll go with the max-heap approach because it's very straightforward
   and readable.  (If they ask for optimal → mention bucket sort O(n) solution)”


   eTime: O(n + m log m) where m ≤ n is number of unique elements
   Worst case ≈ O(n log n)
   Space: O(n) for the map + O(m) for the heap

   Follow-up question they often ask
   Interviewer: “Can we do better than O(n log n)?”
   You: “Yes — we can use bucket sort / frequency bucket approach in O(n) time.”
*/

#include <bits/stdc++.h>

using namespace std;


class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        vector<int> result;

        // map of key, count of key - count frequency of each element
        unordered_map<int,int> keyToCountMap;

        for (auto& number: nums)
            // operator[](key) - Returns a reference to the value that is mapped to key
            // or performing an insertion if such key does not already exist.
            keyToCountMap[number]++;

        // priority queue with largest at top.
        // pair<first, second> = <frequency, number>
        priority_queue<pair<int,int>, vector<pair<int,int>>, less<pair<int,int>>> pq;

        cout << "key2Count: \n";
        for (auto& [key,count]: keyToCountMap)
        {
            pq.push({count, key});
            cout << "key: " << key << " -> " << "count: " << count << endl;
        }
        
        cout << "DEBUG: print pq: ";
        priority_queue<pair<int,int>, vector<pair<int,int>>, less<pair<int,int>>> copy(pq);
        while (!copy.empty())
        {
            pair<int,int> i = copy.top();
            cout << format("<{},{}> ", i.first, i.second);
            copy.pop();            
        }
        cout << endl;
        
        cout << format("max pq: pair<count,key>, k={} elements\n", k);

        int num_elems = 0;
        while(!pq.empty() && num_elems < k)
        {
            auto& p = pq.top();
            result.push_back(get<1>(p));
            cout << get<0>(p) << " -> " << get<1>(p) << endl;
            pq.pop();
            num_elems++;
        }
        
        return result;
    }
};

int main(void)
{
    vector<tuple<vector<int>, int, vector<int>>> testCases
        {//   input vec              k  output
            { {1,1,1,2,2,3},         2, {1,2} },
            { {1},                   1, {1}   },
            { {1,2,1,2,1,2,3,1,3,2}, 1, {1}   },
        };
    
    Solution s;
    for (auto& testCase: testCases)
    {
        cout << "input: k=" << get<1>(testCase) << " vec: ";
        for (auto& i: get<0>(testCase)) cout << i << " ";
        cout << endl;
        
        vector<int> result = s.topKFrequent(get<0>(testCase), get<1>(testCase));
        
        cout << "result [";
        for (auto& i: result) cout << i << ",";
        cout << "]" << endl;
        cout << setfill('-') << setw(30) << "-" << endl;
    }

    return 0;
}