Sorting Elements of an Array by Frequency

JavaView on GFG

Intuition

Sort elements by frequency (descending). For equal frequency, sort by value (ascending or first occurrence).

Algorithm

1Count frequencies. Sort with custom comparator: primary=freq desc, secondary=value asc.

Common Pitfalls

•Stable sort ensures consistent ordering for equal frequencies. Use HashMap for frequencies.

Sorting Elements of an Array by Frequency.java

Java

// Approach: Frequency map, then custom sort: by frequency descending, then by value ascending.
// Time: O(n log n) Space: O(n)
import java.util.*;

class Solution {
    // Function to sort the array according to frequency of elements.
    public ArrayList<Integer> sortByFreq(int arr[]) {
        HashMap<Integer, Integer> map = new HashMap<>();
        ArrayList<Integer> list = new ArrayList<>();

        for (int i = 0; i < arr.length; i++) {
            map.put(arr[i], map.getOrDefault(arr[i], 0) + 1);
        }

        List<Map.Entry<Integer, Integer>> mapList = new LinkedList<>(map.entrySet());

        mapList.sort((a, b) -> {
            int freqCompare = b.getValue().compareTo(a.getValue());
            int valueCompare = a.getKey().compareTo(b.getKey());
            if (freqCompare == 0) {
                return valueCompare;
            } else {
                return freqCompare;
            }
        });

        for (Map.Entry<Integer, Integer> entry : mapList) {
            for (int i = 0; i < entry.getValue(); i++) {
                list.add(entry.getKey());
            }
        }

        return list;
    }
}

Was this solution helpful?