C++: Sort Array by Increasing Frequency

Thought Process

To sort the array based on the frequency of elements in ascending order, we can use a map to store the frequency of each element. Then, we convert the map into a vector of pairs, where each pair contains an element and its frequency. We sort this vector of pairs based on the frequency in ascending order. If two elements have the same frequency, we sort them in descending order of their values. Finally, we reconstruct the sorted array by iterating through the sorted vector of pairs and appending elements according to their frequency. 

class Solution {
public:
    bool static cmp(pair<int,int> a, pair<int,int> b){
    
        if(a.second == b.second)
            return b.first < a.first; 
        else
            return a.second < b.second;
    }
    vector<int> frequencySort(vector<int>& nums) {
            
        // Store frequency in a Map
        map<int,int> mp;
        for(int i=0;i<nums.size();i++){
            int x = nums[i];
            mp[x]++;
        }
    
        // Put all the entities of the map into pair of vectors
        vector<pair<int,int>> vp;
        for(auto entity : mp){
            vp.push_back(entity);
        }
        // Sort the vector as per condition given in question
        sort(vp.begin(),vp.end(),cmp);
    
        // Finally, put the answer in the required format.
        vector<int> ans;
        for(int i=0;i<vp.size();i++){
    
            int val  = vp[i].first;
            int freq = vp[i].second;
    
            while(freq>0){
                ans.push_back(val);
                freq--;
            }  
        }
        return ans;
    }
};

Code Complexity

Time Complexity: O(n log n)

The algorithm involves sorting the vector of pairs, which takes O(n log n) time, where 'n' is the number of unique elements in the array. Additionally, iterating through the array to count frequencies and reconstruct the sorted array takes O(n) time.

Space Complexity: O(n)

The algorithm uses extra space to store the frequency map and the vector of pairs. In the worst case, this space is proportional to the number of unique elements in the array.

Code copied!