Daily Dose of DSA - Day 1

#include <bits/stdc++.h>
using namespace std;
//
bool compare(pair<int, int> p1, pair<int, int> p2) 
//comparator function for vector method
{
    if (p1.second == p2.second)
        return p1.first < p2.first;

    return p1.second > p2.second;
}

struct mycmp
{
bool operator()(pair<int,int>p1,pair<int,int>p2)
/*different than vector comparator , In priority queue constructor we expect  class template*/
//comparator function for priority queue method

{
 if(p1.second==p2.second)
 return p1.first>p2.first;  /*here comparison is done differently than vector method because in case of priority queue , its max heap (larger element at top*/

 return p1.second<p2.second;
}
};

void kmostfrequentnumbers(int arr[], int k, int n)
// using unordered map and pair of vectors
{

    unordered_map<int, int> m; //create key value map
    for (int i = 0; i < n; i++) //O(n)
    {
        m[arr[i]]++;
    }

    vector<pair<int, int>> v(m.begin(), m.end());
    sort(v.begin(), v.end(), compare); //O(nlogn)

    for (int i = 0; i < k; i++) //O(klogn)
    {
        cout << v[i].first << " "; 
    }
}

void kmostfruequentnumbersusingpq(int arr[],int k,int n)
{
//using unordered map and priority queue
  unordered_map<int,int>m; //O(n)
  for(int i=0;i<n;i++)
  m[arr[i]]++; 

  priority_queue<pair<int,int>,vector<pair<int,int>>,mycmp> //O(n)
  pq(m.begin(),m.end());

  for(int i=0;i<k;i++)  //O(klogn)
  {
   cout<<pq.top().first;
   pq.pop();
  }


}

int main()
{
    int arr[] = {20, 40, 30, 20, 30, 40, 60, 60}, k = 3;
    int n = sizeof(arr[n] / arr[0]);
    kmostfrequentnumbers(arr, k, n);
}