Sort Array By Increasing Frequency - Leetcode Solution

The problem "Sort Array By Increasing Frequency" on Leetcode is as follows:

Given an array of integers nums, sort the array in increasing order based on the frequency of the values. If multiple values have the same frequency, sort them in decreasing order.

Example 1:

Input: nums = [1,1,2,2,2,3] Output: [3,1,1,2,2,2] Explanation: '3' has a frequency of 1, '1' has a frequency of 2, and '2' has a frequency of 3. Example 2:

Input: nums = [2,3,1,3,2] Output: [1,2,2,3,3] Explanation: '1' has a frequency of 1, '2' has a frequency of 2, and '3' has a frequency of 2.

To solve this problem, we need to count the frequency of each element in the array and then sort the array based on the frequency. We can accomplish this by using a hashmap to count the frequency. Then, we can create a custom comparator function that compares the frequency of two elements and sorts them accordingly.

The solution to the problem can be broken down into the following steps:

1. Create a hashmap to count the frequency of each element in the array.
2. Create a custom comparator function that sorts two elements based on their frequency and value.
3. Sort the array using the custom comparator created in step 2.

Here's the code to solve the problem:

class Solution {
  public int[] frequencySort(int[] nums) {
    Map<Integer, Integer> freq = new HashMap<>();
    for (int num : nums) {
      freq.put(num, freq.getOrDefault(num, 0) + 1);
    }

    Arrays.sort(nums, new Comparator<Integer>() {
      public int compare(Integer a, Integer b) {
        if (freq.get(a) != freq.get(b)) {
          return freq.get(a) - freq.get(b);
        } else {
          return b - a;
        }
      }
    });

    return nums;
  }
}

Time Complexity: O(NlogN), where N is the length of the array. Space Complexity: O(N), where N is the length of the array.

1