Home » Technical Interview Questions » Array Interview Questions » Sort Elements by Frequency of Occurrences

Sort Elements by Frequency of Occurrences


Reading Time - 2 mins

In sort elements by frequency of occurrences problem, we have given an array a[]. Sort array elements in such a way that the element with the highest number of occurrences comes first. If the number of occurrences is equal then the print the number which appeared first in the array.

Input Format

First-line containing an integer value N.

Second-line containing N integer values.

Output Format

Print input array elements in a single line. such a way that the frequency of a[i] is greater than or equal to the frequency of a[i+1].

Constraints

  • 1<=N<=100000
  • -1e9<=arr[i]<=1e9

Explanation for Sort Elements by Frequency of Occurrences

The question involves two prime problems

  • Sorting via frequency and
  • Maintaining order for resolving clash.

We make use of two advanced and powerful data structures namely :

MAP  and  MULTIPMAP.

Map has the property of mapping some key to the value. Multimap does the same function but in addition to maps, it maintains the key in sorted fashion and specific order. Exactly the function we require.

Algorithm for Sort Elements by Frequency of Occurrences

1.  Add the elements in the map ( map<int, int> ).
     a. If they are not present then add them and make the count 1.
     b. Else increment the count of the value by 1 as it occurred again. Map makes <value, frequency> pairs.

READ  Find a sorted subsequence of size 3 in linear time

2.  Now traverse the map and keep adding the elements into multimap in this way :
     a. Make the 2nd field of map i.e the frequency of the map, as the key of multimap so that we get it automatically sorted.
     b. Map the first value to the second so each entry in multimap holds <frequency, value> in ascending order on frequency.

3. Now simply traverse the multimap in reverse order to get the desired output.

C++ Program for Sort Elements by Frequency of Occurrences

#include <bits/stdc++.h>
using namespace std;
typedef multimap<int, int> MapType;
int main()
{
    int N;
    cin>>N;
    int a[N];
    for(int i=0;i<N;i++)
    {
       cin>>a[i];
    }
    //Map uses the first id as the array element and second as the count of occurrences of the element 
    map<int,int> mp; 
    for(int i=0;i<N;i++)
    {
        //if the array element is present then just increase the count of occurence of it by 1 
        if(mp.find(a[i])!=mp.end()){ 
            mp[a[i]]++;
        }
        else{
            //if the array element is not present in the map already then add it
            mp[a[i]]=1; 
        }
    }
    //it maintains specific order and count  and while inserting makes it sorted
    multimap<int,int> mp2; 
    map<int,int>::iterator it;
    for(it=mp.begin();it!=mp.end();it++){
      //Second becomes the key as we need to sort according to frequency.
      mp2.insert(MapType::value_type(it->second,it->first)); 
    }
    map<int,int>::reverse_iterator itr;
    for(itr=mp2.rbegin();itr!=mp2.rend();itr++)
    {
        //Reverse the multimap and print so that it prints in decreasing order.
        for(int i=0;i<itr->first;i++)
            cout<<itr->second<<"\t";
    }  
    return 0;
}
8
2 5 2 8 5 6 8 8
8 8 8 2 2 5 5 6

Complexity Analysis for Sort Elements by Frequency of Occurrences

Time Complexity

O(NlogN) where N is the number of elements present in the array. Here we arrange elements in sorted multimap.

Space Complexity

O(N) because here we use multimap and map which have maximum size up to N.

READ  Three way partitioning of an array around a given range

References

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions