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.

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);
            outputArray.add(current);
        }
        // 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.

Space Complexity

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

References