Sort Elements by Frequency II  

Difficulty Level Medium
Frequently asked in Amazon Oracle Zoho Zycus
Array Hashing HashMap Sorting

Problem Statement  

In the “Sort Elements by Frequency II” problem we have given an array a[]. Sort the array according to the frequency of the elements where the higher frequency element comes first then others.

Input Format  

The first and only one line containing an integer n.

Second-line containing n space-separated integers.

Output Format  

The first and only one line containing n space-separated integers which is denoting the sorted array on the basis of freq of elements.

Please click Like if you loved this article?

Constraints  

  • 1<=n<=10^5
  • 1<=a[i]<=10^9

Example  

7
1 4 4 4 2 2 7
4 4 4 2 2 1 7

Explanation: Here the freq of 4 is 3, freq of 2 is 2 and the freq of 1,7 is 1. So, the order of sorting is 4, 4, 4, 2, 2, 1, 7.

Algorithm  

  1. We insert all elements and their counts into a hash. This step takes O(n) time where n is the number of elements.
  2. We copy the contents of hash to an array (or vector) and sort them by counts. This step takes O(m log m) time where m is the total number of distinct elements.
  3. For maintaining the order of elements if the frequency is the same, we use another hash that has the key as elements of the array and value as the index. If the frequency is the same for two elements then sort elements according to the index.
See also
Find the smallest positive integer value that cannot be represented as sum of any subset of a given array

Implementation  

C++ Program to Sort Elements by Frequency II

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

bool sortByVal(const pair<int, int>& a, const pair<int, int>& b)
{
    if (a.second == b.second) 
  {
      return a.first < b.first;
  }
  return a.second > b.second;
}

vector<int>sortfreq(int a[], int n)
{
    vector<int>res;
    unordered_map<int, int> m;
    vector<pair<int, int> > v;
    for (int i = 0; i < n; ++i) 
    {
        m[a[i]]++;	 
    }
    copy(m.begin(), m.end(), back_inserter(v));
    sort(v.begin(), v.end(), sortByVal);
    for (int i = 0; i < v.size(); ++i) 
    {
        while(v[i].second--)
        {
            res.push_back(v[i].first);
        }
    }
    return res;
}
int main()
{
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    vector<int>res;
    res = sortfreq(a,n);
    for(auto u: res)
    {
        cout<<u<<" ";
    }
    return 0;
}
8
1 4 4 2 2 2 8 8
2 2 2 4 4 8 8 1

Complexity Analysis to Sort Elements by Frequency II  

Time Complexity

O(n) + O(m Log m) where n is the total number of elements and m is the total number of distinct elements.

Space Complexity

O(n) we create this much space to store the answer.

Please click Like if you loved this article?