Sort Array by Increasing Frequency 🙌📈.
Intuition\nWhen faced with the task of sorting elements based on their frequency, the first thought is to count how often each element appears. Once we know the
# Intuition\nWhen faced with the task of sorting elements based on their frequency, the first thought is to count how often each element appears. Once we know the frequency, the problem becomes a matter of sorting based on these frequencies. If two elements have the same frequency, we then use their values to determine their order.\n\n# Approach\n1. Frequency Counting: Use a HashMap to count the frequency of each number in the array.\n2. Boxing for Custom Sorting: Convert the primitive int array to an Integer array. This allows us to use a custom comparator.\n3. Custom Sorting: Sort the array using a custom comparator that sorts primarily by frequency (increasing order) and secondarily by value (decreasing order).\n4. Unboxing: Convert the Integer array back to a primitive int array.\n\n# Complexity\n### Time complexity: $$O(n)$$\n- Counting frequencies takes $$O(n)$$.\n- Sorting the array takes $$O(nlogn)$$.\n- Unboxing the array takes $$O(n)$$.\n\n### Space complexity: $$O(n)$$\n- The frequency map takes $$O(n)$$ space.\n- The boxed array takes $$O(n)$$ space.\n\n# Code\n```\nclass Solution {\n    public int[] frequencySort(int[] nums) {\n        Map<Integer, Integer> mp = new HashMap<>();\n        for (int num : nums) {\n            mp.put(num, mp.getOrDefault(num, 0) + 1);\n        }\n        \n        Integer[] numsBoxed = Arrays.stream(nums).boxed().toArray(Integer[]::new);\n        \n        Arrays.sort(numsBoxed, (a, b) -> {\n            int freA = mp.get(a);\n            int freB = mp.get(b);\n            if (freA != freB) {\n                return Integer.compare(freA, freB);\n            } else {\n                return Integer.compare(b, a);  \n            }\n        });\n        \n        for (int i = 0; i < nums.length; i++) {\n            nums[i] = numsBoxed[i];\n        }\n        \n        return nums;\n    }\n}\n```
['Array', 'Hash Table', 'Java']