easy Sort Array by Increasing Frequency

Problem Statement

Given an array nums containing the integers, return the resultant array after sorting it in increasing order based on the frequency of the values. If two numbers have the same frequency, they should be sorted in descending numerical order.

Examples

Example 1:

Input: nums = [4, 4, 6, 2, 2, 2]
ExpectedOutput: [6, 4, 4, 2, 2, 2]
Justification: Here, '6' appears once, '4' appears twice, and '2' appears three times. Thus, numbers are first sorted by frequency and then by value when frequencies tie.

Example 2:

Input: nums = [0, -1, -1, -1, 5]
ExpectedOutput: [5, 0, -1, -1, -1]
Justification: '5' and '0' appears once, and '-1' appears three times. After sorting by frequency and resolving ties by sorting in descending order, the result is obtained.

Example 3:

Input: nums = [10, 10, 10, 20, 20, 30]
ExpectedOutput: [30, 20, 20, 10, 10, 10]
Justification: Here, '30' has the lowest frequency, followed by '20', and '10' has the highest frequency. They are sorted accordingly.

Constraints:

1 <= nums.length <= 100
-1000 <= nums[i] <= 1000

Try it yourself

Try solving this question here:

✅ Solution Sort Array by Increasing Frequency

Problem Statement

Examples

Example 1:

Input: nums = [4, 4, 6, 2, 2, 2]
ExpectedOutput: [6, 4, 4, 2, 2, 2]
Justification: Here, '6' appears once, '4' appears twice, and '2' appears three times. Thus, numbers are first sorted by frequency and then by value when frequencies tie.

Example 2:

Input: nums = [0, -1, -1, -1, 5]
ExpectedOutput: [5, 0, -1, -1, -1]
Justification: '5' and '0' appears once, and '-1' appears three times. After sorting by frequency and resolving ties by sorting in descending order, the result is obtained.

Example 3:

Input: nums = [10, 10, 10, 20, 20, 30]
ExpectedOutput: [30, 20, 20, 10, 10, 10]
Justification: Here, '30' has the lowest frequency, followed by '20', and '10' has the highest frequency. They are sorted accordingly.

Constraints:

1 <= nums.length <= 100
-1000 <= nums[i] <= 1000

Solution

To solve this problem, we use a combination of sorting and hashmap data structures. A hashmap is utilized to count the frequency of each element in the array. The key of this approach lies in sorting the array not by the numerical values directly but by the frequency of these values as stored in the hashmap. For values with identical frequencies, a secondary sort criterion is used where numbers are sorted in descending order. This method ensures that we can efficiently sort the array according to the specified rules and handle ties in frequency properly.

Step-by-step Algorithm

Count Frequencies:
- Create a HashMap (freqMap) to store each number's frequency from the array.
- Iterate through the array, incrementing the count for each number in the freqMap.
Merge Sort Algorithm:
- Base Case: If the current segment (subarray) of the array has only one element or is empty, return immediately as a single element or an empty segment is inherently sorted.
- Recursive Sort:
  - Divide the array into two halves.
  - Recursively apply merge sort to the left half.
  - Recursively apply merge sort to the right half.
- Merge Step:
  - Combine the two sorted halves into a single sorted segment using the merge function, which sorts by frequency and value as described.
Merge Function:
- Initialize Pointers: Start with two pointers, one for each half, and a temporary array to build the merged list.
- Comparison and Merging:
  - Compare elements from the two halves.
    - By Frequency: Place the element with the lower frequency in the temporary array first.
    - By Value on Tie: If frequencies are the same, place the element with the higher numerical value first.
  - Move the pointer forward in the half from which the element was taken.
- Append Remaining Elements: Once one half is exhausted, append all remaining elements from the other half.
- Copy to Original: Copy the elements from the temporary array back to the original array segment.
Final Assembly:
- After the top-level merge is completed, the array is fully sorted as per the given criteria.

Algorithm Walkthrough

Let's consider the Input: nums = [4, 4, 6, 2, 2, 2]

Initial Setup:

Array: [4, 4, 6, 2, 2, 2]
freqMap shows frequencies:
- 4 -> 2
- 6 -> 1
- 2 -> 3

Divide and Conquer with Merge Sort:

Step 1: Splitting the Array

Split the array into two halves: [4, 4, 6] and [2, 2, 2]

Step 2: Further Split Left Half [4, 4, 6]

Split [4, 4, 6] into [4, 4] and [6].

Merge Sort on [4, 4]

Since all elements are the same and it’s already sorted by our criteria, this part needs no further action.

Merge Sort on [6]

A single-element array is inherently sorted.

Step 3: Merging [4, 4] and [6]

Compare:
- 4 (freq = 2) and 6 (freq = 1).
Since 6 has a lower frequency, it comes first.
Resulting merged array: [6, 4, 4]

Step 4: Right Half [2, 2, 2]

All elements are the same and thus, no sorting needed.

Final Step: Merging [6, 4, 4] and [2, 2, 2]

Compare:
- 6 (freq = 1) from the left with 2 (freq = 3) from the right.
6 comes first because of the lower frequency.
4 also has a lower frequency than 2 and they follow 6.
Resulting final sorted array after merging: [6, 4, 4, 2, 2, 2]

Code

java

import java.util.*;

class Solution {

  // Method to sort the array based on frequency
  public int[] frequencySort(int[] nums) {
    // Step 1: Count frequency
    Map<Integer, Integer> freqMap = new HashMap<>();
    for (int num : nums) {
      freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
    }

    // Step 2: Use merge sort for custom sorting
    mergeSort(nums, 0, nums.length - 1, freqMap);

    return nums;
  }

  // Merge Sort Function
  private void mergeSort(
    int[] nums,
    int left,
    int right,
    Map<Integer, Integer> freqMap
  ) {
    if (left < right) {
      int mid = (left + right) / 2;
      mergeSort(nums, left, mid, freqMap);
      mergeSort(nums, mid + 1, right, freqMap);
      merge(nums, left, mid, right, freqMap);
    }
  }

  // Merge Function
  private void merge(
    int[] nums,
    int left,
    int mid,
    int right,
    Map<Integer, Integer> freqMap
  ) {
    // Temporary arrays to hold the values
    int[] leftArray = Arrays.copyOfRange(nums, left, mid + 1);
    int[] rightArray = Arrays.copyOfRange(nums, mid + 1, right + 1);

    int i = 0,
      j = 0,
      k = left;
    while (i < leftArray.length && j < rightArray.length) {
      // Comparing frequencies and values for sorting
      if (
        freqMap.get(leftArray[i]) < freqMap.get(rightArray[j]) ||
        (freqMap.get(leftArray[i]).equals(freqMap.get(rightArray[j])) &&
          leftArray[i] > rightArray[j])
      ) {
        nums[k] = leftArray[i];
        i++;
      } else {
        nums[k] = rightArray[j];
        j++;
      }
      k++;
    }

    // Copy the remaining elements of leftArray, if any
    while (i < leftArray.length) {
      nums[k] = leftArray[i];
      i++;
      k++;
    }

    // Copy the remaining elements of rightArray, if any
    while (j < rightArray.length) {
      nums[k] = rightArray[j];
      j++;
      k++;
    }
  }

  public static void main(String[] args) {
    Solution solution = new Solution();

    // Test Cases
    int[] nums1 = { 4, 4, 6, 2, 2, 2 };
    System.out.println(Arrays.toString(solution.frequencySort(nums1))); // [6, 4, 4, 2, 2, 2]

    int[] nums2 = { 0, -1, -1, -1, 5 };
    System.out.println(Arrays.toString(solution.frequencySort(nums2))); // [5, 0, -1, -1, -1]

    int[] nums3 = { 10, 10, 10, 20, 20, 30 };
    System.out.println(Arrays.toString(solution.frequencySort(nums3))); // [30, 20, 20, 10, 10, 10]
  }
}

Complexity Analysis

Time Complexity

Frequency Counting: The frequency of each element is counted using a loop that iterates through each element of the array, which takes time where (n) is the number of elements in the array.
Merge Sort:
- Divide Step: The array is recursively divided into two halves until each subarray contains a single element. This division takes place logarithmically relative to the length of the array, resulting in divisions.
- Conquer Step: Each merge operation for two halves takes time, as each element is considered once for merging. Since merge sort merges at each level of recursion, and each level operates over the entire array, the merge operations at each level of recursion together also take time.

Combining these two steps, the merge sort operation results in a time complexity of .

Therefore, the overall time complexity of the algorithm is: This is because the sorting dominates the frequency counting in terms of time complexity.

Space Complexity

Frequency Map: The space required for storing the frequency of each unique element is , where (k) is the number of unique elements. In the worst case, where all elements are unique, this becomes .
Merge Sort:
- Temporary Arrays: The merge operation uses temporary arrays to hold the elements being merged. The size of these arrays collectively is equal to the size of the array being sorted, which is .
Recursion Stack: Merge sort is a recursive algorithm. The space used by the call stack during the recursive calls depends on the depth of the recursion tree, which is .

Combining the space required for the frequency map, the temporary arrays, and the recursion stack, the total space complexity of the algorithm is: This space complexity is mainly dominated by the space needed for the frequency map and the temporary arrays used in the merge operations. The additional space from the recursion stack is relatively minor compared to (O(n)).

🤖 Don't fully get this? Learn it with Claude

Stuck on Sort Array by Increasing Frequency? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🪜 Hint ladder (no spoilers)

Progressively stronger hints — you still solve it.

I'm working on the problem **Sort Array by Increasing Frequency** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🎨 Explain the approach visually

See the technique, not just code.

Explain the optimal approach to **Sort Array by Increasing Frequency** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔍 Review my solution

Catch bugs, edge cases, sub-optimality.

I'll paste my solution to **Sort Array by Increasing Frequency**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔁 Drill the pattern

Lock in recognition with look-alikes.

Give me 2 problems that use the SAME underlying pattern as **Sort Array by Increasing Frequency**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Apple Redistribution into Boxes Sort Vowels in a String →