In a warehouse, a manager would like to sort the items in the stock hackerrank solution

Sort the array elements based on its frequencies

Assumptions - 1. Sort the array based on its natural occurrence in an ascending order

2. If two numbers having same frequencies then sort them based on natural number precedence

Example: - [ 1, 1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 5]
Output: - [ 5, 4, 4, 2, 2, 2, 3, 3, 3, 1, 1, 1, 1, 1]

Solution: -
1. Create a HashMap which stores the array elements and its occurrences
2. Put hashmap into a List where we can apply sorting based on its frequencies using a customized comparator
3. Object Comparision is Java: -
if Obj1 is less then Obj2 then return -1
if Obj1 is equal to Obj2 then return 0
if Obj1 is greater then Obj2 then return +1
4. In our case, if two numbers have the same frequences then we should put the number which has natural precedence in the output
Ex: - if above example, number 2 and 3 occurred 3 times hence 2 should come first

public static void sortTheArrayByFrequency(int[] array){ Map<Integer, Integer> map = new HashMap<>(); //put array elements based on its frequncies for(int i : array){ map.put(i, map.getOrDefault(i,0)+1); } //Put the hashmap into a list where we use customized comparator List<Map.Entry<Integer, Integer>> list = new ArrayList<>(); for(Map.Entry<Integer, Integer> e : map.entrySet()){ list.add(e); } // list looks like [1=5, 2=3, 3=3, 4=2, 5=1] Collections.sort(list, (a, b) -> { // if its ouccrances are same then sort natually //else sort based on freqncies if(a.getValue() == b.getValue()) return a.getKey() - b.getKey(); else return a.getValue() - b.getValue(); }); // list looks like [5=1, 4=2, 2=3, 3=3, 1=5] for(Map.Entry<Integer, Integer> e : list){ int num = e.getValue(); while(num!=0){ System.out.print(e.getKey()+ " "); num--; } } }

Output:-
5 4 4 2 2 2 3 3 3 1 1 1 1 1

Print the elements of an array in the decreasing frequency if 2 numbers have same frequency then print the one which came first.

Examples:

Input: arr[] = {2, 5, 2, 8, 5, 6, 8, 8} Output: arr[] = {8, 8, 8, 2, 2, 5, 5, 6} Input: arr[] = {2, 5, 2, 6, -1, 9999999, 5, 8, 8, 8} Output: arr[] = {8, 8, 8, 2, 2, 5, 5, 6, -1, 9999999}

METHOD 1 (Use Sorting)

Use a sorting algorithm to sort the elements O(nlogn)
Iterate the sorted array and construct a 2D array of element and count O(n).
Sort the 2D array according to count O(nlogn).

Example:

Input 2 5 2 8 5 6 8 8 After sorting we get 2 2 5 5 6 8 8 8 Now construct the 2D array as 2, 2 5, 2 6, 1 8, 3 Sort by count 8, 3 2, 2 5, 2 6, 1

How to maintain the order of elements if the frequency is the same?

The above approach doesn’t make sure the order of elements if the frequency is same. To handle this, we should use indexes in step 3, if two counts are same then we should first process(or print) the element with a lower index. In step 1, we should store the indexes instead of elements.

Input 2 5 2 8 5 6 8 8 After sorting we get Element 2 2 5 5 6 8 8 8 Index 0 2 1 4 5 3 6 7 Now construct the 2D array as Index, Count 0, 2 1, 2 5, 1 3, 3 Sort by count (consider indexes in case of tie) 3, 3 0, 2 1, 2 5, 1 Print the elements using indexes in the above 2D array.

Below is the implementation of above approach –

 
bool mycomp(struct ele a, struct ele b)

bool mycomp2(struct ele a, struct ele b)

        return (a.count < b.count);

        return a.index > b.index;

void sortByFrequency(int arr[], int n)

    for (int i = 0; i < n; i++) {

    stable_sort(element, element + n, mycomp);

    for (int i = 1; i < n; i++) {

        if (element[i].val == element[i - 1].val) {

            element[i].count += element[i - 1].count + 1;

            element[i - 1].count = -1;

            element[i].index = element[i - 1].index;

    stable_sort(element, element + n, mycomp2);

    for (int i = n - 1, index = 0; i >= 0; i--)

        if (element[i].count != -1)

            for (int j = 0; j < element[i].count; j++)

                arr[index++] = element[i].val;

    int arr[] = { 2, 5, 2, 6, -1, 9999999, 5, 8, 8, 8 };

    int n = sizeof(arr) / sizeof(arr[0]);

    for (int i = 0; i < n; i++)

Output:

8 8 8 2 2 5 5 6 -1 9999999

Thanks to Gaurav Ahirwar for providing above implementation.

METHOD 2 (Use Hashing and Sorting) Using a hashing mechanism, we can store the elements (also first index) and their counts in a hash. Finally, sort the hash elements according to their counts.

Below is the implementation of above approach –

 
bool fcompare(pair<int, pair<int, int> > p,

              pair<int, pair<int, int> > p1)

    if (p.second.second != p1.second.second)

        return (p.second.second > p1.second.second);

        return (p.second.first < p1.second.first);

void sortByFrequency(int arr[], int n)

    unordered_map<int, pair<int, int> > hash;

    for (int i = 0; i < n; i++) {

        if (hash.find(arr[i]) != hash.end())

            hash[arr[i]] = make_pair(i, 1);

    vector<pair<int, pair<int, int> > > b;

    for (it; it != hash.end(); ++it)

        b.push_back(make_pair(it->first, it->second));

    sort(b.begin(), b.end(), fcompare);

    for (int i = 0; i < b.size(); i++) {

        int count = b[i].second.second;

            cout << b[i].first << " ";

    int arr[] = { 2, 5, 2, 6, -1, 9999999, 5, 8, 8, 8 };

    int n = sizeof(arr) / sizeof(arr[0]);

 
import java.util.Collections;

import java.util.Comparator;

import java.util.HashMap;

    static Integer[] arr = { 2, 5, 2, 8, 5, 6, 8, 8 };

    public static void main(String[] args)

        List<Integer> list = Arrays.asList(arr);

        sortBasedOnFrequencyAndValue(list);

    sortBasedOnFrequencyAndValue(List<Integer> list)

        final HashMap<Integer, Integer> mapCount

            = new HashMap<Integer, Integer>();

        final HashMap<Integer, Integer> mapIndex

            = new HashMap<Integer, Integer>();

        for (int i = 0; i < n; i++) {

            if (mapCount.containsKey(arr[i])) {

                             mapCount.get(arr[i]) + 1);

        Collections.sort(list, new Comparator<Integer>() {

            public int compare(Integer n1, Integer n2)

                int freq1 = mapCount.get(n1);

                int freq2 = mapCount.get(n2);

        System.out.println(list);

from collections import defaultdict

d = defaultdict(lambda: 0)

arr.sort(key=lambda x: (-d[x], x))

if __name__ == "__main__":

arr = [2, 5, 2, 6, -1, 9999999, 5, 8, 8, 8]

solution = sortByFreq(arr, n)

 
let arr=[2, 5, 2, 6, -1, 9999999, 5, 8, 8, 8];

function sortBasedOnFrequencyAndValue(list)

        for (let i = 0; i < n; i++) {

            if (mapCount.has(arr[i])) {

                             mapCount.get(arr[i]) + 1);

        list.sort(function(n1,n2){

                let freq1 = mapCount.get(n1);

                let freq2 = mapCount.get(n2);

        document.write(list.join(" "));
sortBasedOnFrequencyAndValue(arr);

Output:

8 8 8 2 2 5 5 6 -1 9999999

This can also be solved by Using two maps, one for array element as an index and after this second map whose keys are frequency and value are array elements.

METHOD 3(Use BST and Sorting)

Insert elements in BST one by one and if an element is already present then increment the count of the node. Node of the Binary Search Tree (used in this approach) will be as follows.

Store the first indexes and corresponding counts of BST in a 2D array.
Sort the 2D array according to counts (and use indexes in case of tie).

Time Complexity: O(nlogn) if a Self Balancing Binary Search Tree is used. This is implemented in Set 2. https://youtu.be/NBXf9vCksuM

Set 2:

Sort elements by frequency | Set 2
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above

Article Tags :

Practice Tags :