Sort Array by Increasing Frequency [ C++] 96% faster solution
Intuition\n Describe your first thoughts on how to solve this problem. \nFirsly as we see frequecy the intuition is to use map. We store the freq in map and the
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nFirsly as we see frequecy the intuition is to use map. We store the freq in map and then think of how to use heap for sorting.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nMap stores te frequency of each element so we iterate through the map and push into the min heap the elements one by one based on frequency but there is a catch where two elements have same frequency they need to be arranged in descending order so we need a special comparator to perform this operation on heap.\nSo we make use of \nbool operator()(pair<int,int> a,pair<int,int> b)\n{\n    if(a.first==b.first)\n    {\n        a.second < b.second;\n    }\n    return a.first > b.first;\n}\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n    O(nlogn)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n    O(n)\n\n# Code\n```\nclass MyComp\n{\n    public:\n        bool operator()(pair<int,int> a,pair<int,int> b)\n        {\n            if(a.first==b.first)\n            {\n                return a.second < b.second;\n            }\n            return a.first > b.first;\n\n        }\n};\nclass Solution {\npublic:\n    vector<int> frequencySort(vector<int>& nums) {\n        map<int,int> m;\n        priority_queue<pair<int,int>,vector<pair<int,int>>,MyComp>pq;\n        vector<int> ans;\n        for(int i=0;i<nums.size();i++)\n        {\n            m[nums[i]]++;\n        }\n        for(auto it=m.begin();it!=m.end();it++)\n        {\n                pq.push({it->second,it->first});\n        }\n        while(!pq.empty())\n        {\n            int freq=pq.top().first;\n            int el=pq.top().second;\n            pq.pop();\n            for(int i=0;i<freq;i++)\n            {\n                ans.push_back(el);\n            }\n        }\n        return ans;\n    }\n};\n```
['C++']