Sort Array by Increasing Frequency Leetcode Solution

Problem Statement

Given an array of integers nums, sort the array in increasing order based on the frequency of the values. If multiple values have the same frequency, sort them in decreasing order.

Example

nums = [1,1,2,2,2,3]

[3,1,1,2,2,2]

Explanation:

‘3’ has a frequency of 1, ‘1’ has a frequency of 2, and ‘2’ has a frequency of 3.

nums = [2,3,1,3,2]

[1,3,3,2,2]

Explanation:

‘2’ and ‘3’ both have a frequency of 2, so they are sorted in decreasing order.

Approach

In this problem firstly we have to count the frequencies of each element. For this we can use a hash map in java or unordered set in c++. Now we want our result array to contain those element first which have high frequency.
For this we can sort the given input array now on the basis of its total frequency that we have already stored in the map.

Now we just have to make a comparator outside the function. Here we will be comparing two elements ( lets say a and b) and we know the frequency of each element. So if frequency of a is greater than b then put b before a in the array. The next case will be if frequency of a and b is same then put that element first which have the higher value. Example:

Case 1

Case 2

Algorithm

• Create a hash map.
• Run a loop and for each element increment the count of that element in map by 1.
• Now make a comparator function for comparing two integers using its count stored in the map. Compare two elements and decide their order as discussed above.
• Sort the given array using this comparator.
• Return the sorted array.

Implementation

C++ Program for Sort Array by Increasing Frequency Leetcode Solution

#include <bits/stdc++.h>
using namespace std;

bool comp(pair<int,int> p1,pair<int,int> p2)
{
    if(p1.second == p2.second) return p1.first > p2.first;
    return p1.second < p2.second;
}

vector<int> frequencySort(vector<int>& nums) 
{
    unordered_map<int,int> m;
    for(auto x:nums) m[x]++;

    vector<pair<int,int> > v;

    for(auto p:m) v.push_back(p);

    sort(v.begin(),v.end(), comp);

    vector<int> res;
    for(auto p:v)
    {
        while(p.second--)
            res.push_back(p.first);
    }

    return res;        
}

int main() 
{
    vector<int> nums = {2,3,1,3,2};
    for(int x: frequencySort (nums))
        cout<<x<<" ";
    return 0; 
}

1 3 3 2 2

Java Program for Sort Array by Increasing Frequency Leetcode Solution

import java.util.*;
import java.lang.*;

class Comp implements Comparator<Integer>{
    Map<Integer,Integer>map=Rextester.map;
    public int compare(Integer a,Integer b){
        if(map.get(a)>map.get(b))return 1;
        else if(map.get(b)>map.get(a))return -1;
        else{
            if(a>b)return -1;
            else if(a<b)return 1;
            return 0;
        }
    }
}
class Rextester
{  
    static Map<Integer,Integer>map;
    public static int[] frequencySort(int[] nums)
    {
        map=new HashMap<Integer,Integer>();
        for(int i:nums){
            if(map.containsKey(i)){
                map.put(i,1+map.get(i));
            }else{
                map.put(i,1);
            }
        }
        Integer[]arr=new Integer[nums.length];
        int k=0;
        for(int i:nums){
            arr[k++]=i;
        }
        Arrays.sort(arr,new Comp());
        k=0;
        for(int i:arr){
            nums[k++]=i;
        }
        return nums;
    }
    
    public static void main(String args[])
    {
        int[]nums={1,1,2,2,2,3};
        nums=frequencySort(nums);
        for(int i:nums)
        {
            System.out.print(i+" ");
        }
    }
}

1 3 3 2 2

Complexity Analysis for Sort Array by Increasing Frequency Leetcode Solution

Time Complexity

O(nlog(n)): where n is the size of the input array. Insertion and access in hash map takes O(n) time for n elements and sorting takes nlogn time. Hence time complexity will be nlogn.

Space Complexity 

O(n) : At worst their can be n different elements in the array. Thus size of the map will be O(n).