Sort Array by Increasing Frequency

Java: Sort Array by Increasing Frequency

Thought Process

Note: The aim of this question is to get familiar with converting an array to a list and list to an array.

First, we convert the input array into a List using Java Streams. Then, we create a HashMap to store the frequency of each element by iterating through the list. The key sorting logic comes next i.e. we use Collections.sort() with a custom comparator that first compares frequencies in ascending order, and for elements with equal frequencies, compares their values in descending order. Finally, we convert the sorted list back to an array using streams and return it as the result.

class Solution {
    public int[] frequencySort(int[] nums) {
      
        // Array to List
        List<Integer> list = Arrays.stream(nums).boxed().collect(Collectors.toList());
              
        // Put elements in the map
        Map<Integer,Integer> mp = new HashMap<>();
        list.stream().forEach(n->mp.put(n,mp.getOrDefault(n,0)+1));
      
        // Sort the list as per the Requirement
        Collections.sort(list, (a,b)->{
                  
            if(mp.get(a) != mp.get(b))
                return Integer.compare(mp.get(a),mp.get(b));
            else
                return Integer.compare(b,a);
            }
        );
              
        // Finally, convert the list into array & return it.
        return list.stream().mapToInt(i->i).toArray();
    }
}

Code Complexity

Time Complexity: O(n log n)

The dominant factor is the sorting operation using Collections.sort(), which has O(n log n) time complexity. The frequency counting and stream operations are O(n) each.

Space Complexity: O(n)

We use additional linear space for the HashMap and the List, along with some constant space for intermediate operations.