# Sort Elements by Frequency of Occurrences

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

## Problem Statement

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.

Search an Element in Sorted Rotated Array

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.

## Implementation

### 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;
}```

### Java Program for Sort Elements by Frequency of Occurrences

```import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;

class SortComparator implements Comparator<Integer> {
private final Map<Integer, Integer> freqMap;

// Assign the specified map
SortComparator(Map<Integer, Integer> tFreqMap)
{
this.freqMap = tFreqMap;
}

// Compare the values
@Override
public int compare(Integer k1, Integer k2)
{

// Compare value by frequency
int freqCompare = freqMap.get(k2).compareTo(freqMap.get(k1));

// Compare value if frequency is equal
int valueCompare = k1.compareTo(k2);

// If frequency is equal, then just compare by value, otherwise -
// compare by the frequency.
if (freqCompare == 0)
return valueCompare;
else
return freqCompare;
}
}
class sum
{
public static void main(String[] args)
{
Scanner sr = new Scanner(System.in);
int n = sr.nextInt();
int arr[] = new int[n];
for(int i=0;i<n;i++)
{
arr[i] = sr.nextInt();
}
Map<Integer, Integer> map = new HashMap<>();
List<Integer> outputArray = new ArrayList<>();
for (int current : arr)
{
int count = map.getOrDefault(current, 0);
map.put(current, count + 1);
}
// Compare the map by value
SortComparator comp = new SortComparator(map);
// Sort the map using Collections CLass
Collections.sort(outputArray, comp);
// Final Output
for (Integer i : outputArray)
{
System.out.print(i + " ");
}
}
}```
```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.