Sorting the elements by frequency

Given an array, how do we sort the elements by descending order of their frequency?

Also if two elements appear for same number of times, one which appeared first in the input array should be placed first.

For example, if A = [7, 6, 1, 7, 1, 3, 6, 6, 2]

The output should be [6, 6, 6, 7, 7, 1, 1, 3, 2]

Solution: First calculate the frequency for the given elements.

Value -> Frequency 6 -> 3 7 -> 2 1 -> 2 3 -> 1 2 -> 1

Then store the elements in a priority queue (max-heap) based on the frequency of values. Then delete the elements from priority queue one by one and add them to resultant array. Here is the Java implementation.

import java.util.*;

public class SortByFrequency {
    public static void main(String []args) {
        int []arr = {5, 1, 5, 1, 1, 7, 8, 4, 8, 2};
        int []freqSorted = sortByFrequency(arr);
        Arrays.stream(freqSorted).forEach(System.out::println);
    }

    private static int[] sortByFrequency(int []arr) {
        //calculate frequencies of elements
        Map<Integer, Integer> freqMap = getFrequencyMap(arr);

        //Comparator for storing value, frequency tuples in priority queue (max heap)
        //Using the Java 8 Lambdas to define comparator
        Comparator< Map.Entry<Integer,Integer> > descFreqComparator = (e1, e2) -> e2.getValue() - e1.getValue();
        PriorityQueue< Map.Entry<Integer, Integer> > pq = new PriorityQueue<>(descFreqComparator);

        //Add map entries to max heap
        for(Map.Entry<Integer, Integer> entry: freqMap.entrySet()) {
            pq.add(entry);
        }

        //Form the result array by deleting elements from priority queue
        int []result = new int[arr.length];
        int i = 0;
        while( !pq.isEmpty() ) {
            Map.Entry<Integer, Integer> entry = pq.poll();
            for(int j = 0; j < entry.getValue(); j++) {
                result[i++] = entry.getKey();
            }
        }
        return result;
    }

    private static Map<Integer, Integer> getFrequencyMap(int []arr) {
        //LinkedHashMap to preserve the original order of elements in arr
        Map<Integer, Integer> freqMap = new LinkedHashMap<>();
        int i;
        for(i = 0; i < arr.length; i++) {
            if(freqMap.containsKey(arr[i])) {
                freqMap.put(arr[i], freqMap.get(arr[i])+1);
            } else {
                freqMap.put(arr[i], 1);
            }
        }
        return freqMap;
    }
}

Time Complexity: O(n log n) because we are using max heap to store the element, frequency pairs for retrieving them in descending order of their frequencies.
Space Complexity: O(n) Extra storage for frequency map and resultant array.

Leave a Reply Cancel reply