Sort elements by frequency

Difficulty Level Easy
Frequently asked in Amazon Oracle Zoho Zycus
Array Hashing SortingViews 3481

Problem Statement

You are given an array of integers, some numbers are repeated in it. The problem statement asks to print the number in the array in decreasing order according to their frequency that is to sort elements by frequency.

Example

arr[]={3,4,3,1,2,9,2,9,2,5 }
2 2 2 3 3 9 9 4 1 5

Explanation: The number here printed is in decreasing order of their frequency. The number 2 has max frequency so printed first, number 3 and number 9 has same frequencies as 2, but 3 comes first in the order so it is printed before 9, and then 4, 1 and 5 having a frequency as 1.

 

Algorithm to sort elements by frequency

1. Declare a map.
2. Count and store the frequency of each number of an array into the map.
3. Select the keys with greater frequencies.
4. Get that frequency into val.
5. Print that key, its frequency number of times that is val.

Explanation

We have given an integer array. We have asked to print the array in decreasing order of frequency. If in an array, any number comes at most x number of times, then that number should be printed x number of times first and then after number having a frequency less than x comes in the sequence. For that, we are going to use hashing. We are going to use the map for that.

We will be using a map, we are going to traverse the array. Then count and store all the numbers in the array with its frequency in a map. If any element is new in the map then make a place for its entry. Then mark its frequency as 1. If it already exists then get its frequency and increase its frequency by 1 and again push it with the same number. Then we can take any data structure to hold our resultant data when we sort the number according to their frequency.

We will be traversing the map. After that we will sort the array according to their frequency decreasingly means the number having higher frequency comes first and also the number with similar frequency comes in order in the sorted array as it comes in the original array. We will pick each key and its value, and we are going to print that key val number of times. If we do not want to print it directly then store it into any data type, here we used a StringBuffer or a vector to store out data, and later on, we can print that data type values. Automatically, we have sorted it so we have the maximum frequency and print that key frequency number of times. And this is how we sort elements by frequency.

Sort elements by frequency

Code

C++ code to sort elements by frequency

#include<iostream>
#include<unordered_map>
#include<vector>
#include<algorithm>
using namespace std;
unordered_map<int, int> map1;
bool sortFrequency(const pair<int, int>& a, const pair<int, int>& b)
{
    if (a.second == b.second)
    {
        return map1[a.first] < map1[b.first];
    }
    return a.second > b.second;
}
void sortByFreq(int a[], int n)
{
    unordered_map<int, int> MAP;
    vector<pair<int, int> > vec;
    for (int i = 0; i < n; ++i)
    {
        MAP[a[i]]++;
        if (!map1.count(a[i]))
            map1[a[i]] = i + 1;
    }
    copy(MAP.begin(), MAP.end(), back_inserter(vec));
    sort(vec.begin(), vec.end(), sortFrequency);
    for (int i = 0; i < vec.size(); ++i)
        for (int j = 0; j < vec[i].second; ++j)
            cout << vec[i].first << " ";
}
int main()
{
    int arr[] = {3,4,3,1,2,9,2,9,2,5 };
    int n = sizeof(arr) / sizeof(arr[0]);
    sortByFreq(arr, n);
    return 0;
}
2 2 2 3 3 9 9 4 1 5

 

Java code to sort elements by frequency

import java.io.IOException;
import java.util.*;

class sortByFrequency
{
    public static StringBuffer sortFrequency(int arr1[], int l1)
    {
        Map<Integer, Integer> sortMap = frequencyMap(arr1, l1);
        StringBuffer output = new StringBuffer();

        sortMap.entrySet().stream()
        .sorted(Map.Entry.<Integer, Integer> comparingByValue().reversed())
        .forEach(e ->
        {
            int key = e.getKey();

            int val = e.getValue();

            for (int i = 0; i < val; i++)
            {
                output.append(key + " ");
            }
        });

        return output;
    }
    private static Map<Integer, Integer> frequencyMap(int[] arr, int l1)
    {
        Map<Integer, Integer> FrequencyMap = new LinkedHashMap<>();
        for (int i = 0; i < l1; i++)
        {
            if (FrequencyMap.containsKey(arr[i]))
            {
                FrequencyMap.put(arr[i], FrequencyMap.get(arr[i]) + 1);
            }
            else
            {
                FrequencyMap.put(arr[i], 1);
            }
        }
        return FrequencyMap;
    }
    public static void main(String[] args)
    {
        int arr[] = { 3,4,3,1,2,9,2,9,2,5 };
        System.out.println(sortFrequency(arr, arr.length));
    }
}

2 2 2 3 3 9 9 4 1 5

Complexity Analysis

Time Complexity

O(n + m Log m) where “n” is the total number of elements in the array and “m” is the total number of distinct elements in the array. The mlogm comes from sorting m elements.

Space Complexity

Since we have used a map and an array to store n elements we have O(n) where “n” is the number of elements in the array.

Translate »