Sort Elements by Frequency II

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

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.

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.

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.

Translate ยป