LeetCode 1636: Sort Array by Increasing Frequency

Explanation

To solve this problem, we can follow these steps:

1. Create a frequency map to store the frequency of each element in the input array.
2. Sort the array based on the frequency of elements in increasing order. If two elements have the same frequency, sort them in decreasing order.
3. Implement a custom comparator to sort the elements based on the above criteria.
4. Finally, return the sorted array.

Time complexity: O(n log n)
Space complexity: O(n)

class Solution {
    public int[] frequencySort(int[] nums) {
        Map<Integer, Integer> freqMap = new HashMap<>();
        for (int num : nums) {
            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
        }
        
        Arrays.sort(nums, (a, b) -> freqMap.get(a).equals(freqMap.get(b)) ? b - a : freqMap.get(a) - freqMap.get(b));
        
        return nums;
    }
}