# Sort Array by Increasing Frequency
**Difficulty:** EASY
[External](https://leetcode.com/problems/sort-array-by-increasing-frequency)
Canonical: https://scaleengineer.com/dsa/problems/sort-array-by-increasing-frequency
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [Agoda](https://scaleengineer.com/companies/agoda), [SAP](https://scaleengineer.com/companies/sap), [tcs](https://scaleengineer.com/companies/tcs), [Akuna Capital](https://scaleengineer.com/companies/akuna-capital)
---
## Problem
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.

Return the _sorted array_.

**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,3,3,2,2]
**Explanation:** '2' and '3' both have a frequency of 2, so they are sorted in decreasing order.

**Example 3:**

**Input:** nums = [-1,1,-6,4,5,-6,1,4,1]
**Output:** [5,-1,4,4,-6,-6,1,1,1]

**Constraints:**

* `1 <= nums.length <= 100`
* `-100 <= nums[i] <= 100`

# Approaches
## Custom Sort with Repeated Frequency Counting
This approach involves sorting the array using a custom comparator. The key idea is that for any two elements being compared during the sort, their frequencies are calculated on the fly by iterating through the entire array. This is highly inefficient as frequency counting is repeated many times, making it a brute-force method.
**Time:** O(N^2 * log N). The sorting algorithm (like MergeSort used by `Arrays.sort`) performs O(N log N) comparisons. Each comparison takes O(N) time to count frequencies, leading to the overall complexity. · **Space:** O(N). An auxiliary array of `Integer` objects is created to facilitate custom sorting.
**Pros:** Conceptually simple, directly implementing the comparison logic.
**Cons:** Extremely inefficient and will likely result in a 'Time Limit Exceeded' error on most platforms for non-trivial input sizes.
### Explanation
This method directly translates the sorting criteria into a Java `Comparator`. We convert the input `int[]` to an `Integer[]` to be able to use `Arrays.sort` with a custom comparator object. The comparator's `compare` method is the core of the logic. For any two numbers `a` and `b`, it performs a full scan of the original array to count occurrences of `a` and another full scan for `b`. This process is repeated for every comparison the sorting algorithm makes. While straightforward to conceptualize, its performance is very poor. ```java import java.util.Arrays; class Solution { public int[] frequencySort(int[] nums) { Integer[] numsObj = new Integer[nums.length]; for (int i = 0; i < nums.length; i++) { numsObj[i] = nums[i]; } Arrays.sort(numsObj, (a, b) -> { long freqA = 0; long freqB = 0; for (int num : nums) { if (num == a.intValue()) freqA++; if (num == b.intValue()) freqB++; } if (freqA != freqB) { return (int) (freqA - freqB); } else { return b - a; } }); for (int i = 0; i < nums.length; i++) { nums[i] = numsObj[i]; } return nums; } } ```
### Algorithm
*   Convert the primitive `int[]` array to an `Integer[]` array to use `Arrays.sort` with a custom comparator. *   Define a custom `Comparator` that takes two numbers, `a` and `b`. *   Inside the comparator, calculate the frequency of `a` by iterating through the entire array. *   Similarly, calculate the frequency of `b`. *   Compare the frequencies. If `freq(a)` is not equal to `freq(b)`, return `freq(a) - freq(b)`. *   If the frequencies are equal, sort by value in descending order by returning `b - a`. *   Apply this sort to the `Integer[]` array. *   Convert the sorted `Integer[]` back to `int[]`.

## Using a HashMap and Custom Sort
A much more efficient approach is to pre-calculate the frequencies of all numbers and store them in a HashMap. This avoids the expensive re-computation of frequencies inside the sort's comparator. We first iterate through the array once to populate the frequency map. Then, we sort the array using a custom comparator that looks up frequencies from this map in constant time on average.
**Time:** O(N log N). It takes O(N) to build the frequency map and O(N log N) to sort the array. Map lookups inside the comparator are O(1) on average. · **Space:** O(N). The HashMap can store up to N unique elements, and an auxiliary `Integer[]` of size N is used for sorting.
**Pros:** A standard and well-understood solution.; Significantly more efficient than the brute-force method.
**Cons:** Involves overhead from using a HashMap and boxing integers.; Not the most optimal solution in terms of time complexity.
### Explanation
The main bottleneck of the previous approach was re-calculating frequencies. We can optimize this by computing all frequencies in a single pass and storing them. A `HashMap` is a suitable data structure for this, mapping each number to its count. After populating the map, we can sort the array (again, as an `Integer[]`) with a custom comparator. This comparator now performs a quick `O(1)` average time lookup in the map to get the frequencies, making the entire sorting process much faster. ```java import java.util.*; 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); } Integer[] numsObj = new Integer[nums.length]; for (int i = 0; i < nums.length; i++) { numsObj[i] = nums[i]; } Arrays.sort(numsObj, (a, b) -> { int freqA = freqMap.get(a); int freqB = freqMap.get(b); if (freqA != freqB) { return freqA - freqB; } else { return b - a; } }); for (int i = 0; i < nums.length; i++) { nums[i] = numsObj[i]; } return nums; } } ```
### Algorithm
*   Create a `HashMap<Integer, Integer>` to store the frequency of each number. *   Iterate through the input array `nums` and populate the map. *   Convert the `int[]` to `Integer[]` to allow sorting with a custom object comparator. *   Sort the `Integer[]` array using `Arrays.sort()` with a custom `Comparator`. *   The comparator logic for two numbers `a` and `b` is: *   Get their frequencies from the HashMap. *   If frequencies differ, return the difference to sort by frequency (increasing). *   If frequencies are equal, return `b - a` to sort by value (decreasing). *   Convert the sorted `Integer[]` back to `int[]`.

## Using a Frequency Array and Custom Sort
This approach is an optimization of the HashMap method, made possible by the problem's constraint on the range of input values (`-100` to `100`). Instead of a HashMap, we use a simple array as a frequency map. This provides faster, guaranteed constant-time lookups without the overhead of hashing, making it slightly more performant in practice.
**Time:** O(N log N). O(N) to build the frequency array and O(N log N) for sorting. Array lookups are O(1). · **Space:** O(N). O(K) for the frequency array where K is the range of values (201, which is constant space O(1)), and O(N) for the `Integer[]` copy.
**Pros:** More efficient than the HashMap approach due to faster array lookups.; Constant space for frequency counting.
**Cons:** Relies on the constraint of a small range of input values.; Still bottlenecked by the O(N log N) comparison sort.
### Explanation
Given that `nums[i]` is between -100 and 100, there are only 201 possible distinct values. We can exploit this by using a fixed-size array instead of a `HashMap` to store frequencies. We map each number `num` to an index `num + 100`. This eliminates the overhead associated with hashing and potential collisions in a `HashMap`, resulting in faster and more consistent performance for frequency lookups. The rest of the logic, involving sorting a temporary `Integer[]` array, remains the same as the previous approach. ```java import java.util.Arrays; import java.util.Comparator; class Solution { public int[] frequencySort(int[] nums) { int[] freq = new int[201]; for (int num : nums) { freq[num + 100]++; } Integer[] numsObj = new Integer[nums.length]; for (int i = 0; i < nums.length; i++) { numsObj[i] = nums[i]; } Arrays.sort(numsObj, (a, b) -> { int freqA = freq[a + 100]; int freqB = freq[b + 100]; if (freqA != freqB) { return freqA - freqB; } else { return b - a; } }); for (int i = 0; i < nums.length; i++) { nums[i] = numsObj[i]; } return nums; } } ```
### Algorithm
*   Create an integer array `frequency` of size 201, using an offset of 100 to map values to indices (`index = value + 100`). *   Iterate through `nums` and populate the `frequency` array. *   Convert `nums` to `Integer[]`. *   Sort the `Integer[]` with a custom `Comparator` that uses the `frequency` array for lookups. *   The comparison logic remains the same: sort by frequency (increasing), then by value (decreasing). *   Convert the sorted `Integer[]` back to `int[]`.

## Bucket Sort by Frequency
The most efficient approach avoids a comparison-based sort, achieving linear time complexity. It uses a 'bucket sort' style algorithm. After counting frequencies, we create 'buckets' for each possible frequency (from 1 to N). Each bucket holds the numbers that appear with that frequency. We then build the result array by iterating through the buckets in order of increasing frequency.
**Time:** O(N). O(N) to count frequencies, O(K) to populate buckets (where K=201 is constant), and O(N) to build the final array. The total complexity is O(N + K), which simplifies to O(N). · **Space:** O(N). O(K) for the frequency array, O(N) for the buckets (as the total number of items across all buckets is the number of unique elements, at most N), and O(N) for the result array.
**Pros:** Optimal linear time complexity.; Efficiently handles all sorting criteria without a comparison sort.
**Cons:** More complex to implement compared to sorting-based solutions.; Uses more auxiliary space for the buckets.
### Explanation
This approach achieves optimal `O(N)` time complexity by avoiding a comparison-based sort. 1.  **Frequency Counting**: First, we count frequencies using an array, just like in the previous approach. 2.  **Bucketing**: We create an array of lists, where the index represents a frequency. `buckets[f]` will hold all numbers that appear `f` times. We iterate through our frequency map. If a number `num` has frequency `f`, we add `num` to `buckets[f]`. To satisfy the secondary sorting condition (decreasing value for same frequency), we can populate the buckets by iterating through the numbers from highest to lowest (100 down to -100). This ensures that for any given frequency, the numbers are added to the bucket in decreasing order automatically. 3.  **Building the Result**: Finally, we iterate through the buckets from frequency 1 up to the maximum possible frequency. For each frequency, we take the numbers from its bucket and append them to our result array the required number of times. ```java import java.util.*; class Solution { public int[] frequencySort(int[] nums) { int[] freq = new int[201]; for (int num : nums) { freq[num + 100]++; } List<Integer>[] buckets = new List[nums.length + 1]; for (int i = 0; i < buckets.length; i++) { buckets[i] = new ArrayList<>(); } for (int i = 200; i >= 0; i--) { if (freq[i] > 0) { int num = i - 100; buckets[freq[i]].add(num); } } int[] result = new int[nums.length]; int index = 0; for (int f = 1; f <= nums.length; f++) { for (int num : buckets[f]) { for (int i = 0; i < f; i++) { result[index++] = num; } } } return result; } } ```
### Algorithm
*   Count frequencies of each number using a frequency array (size 201). *   Create an array of lists (buckets), where `buckets[f]` will store numbers with frequency `f`. The array size is `N + 1`. *   Iterate through the possible numbers (-100 to 100). For each number with frequency `f > 0`, add it to `buckets[f]`. To handle the tie-breaking rule (decreasing value), iterate numbers from 100 down to -100. *   Initialize an empty result array. *   Iterate through the buckets from frequency `f = 1` to `N`. *   For each number `num` in `buckets[f]`, append `num` to the result array `f` times.

# Solutions
### Java

```java
class Solution {
public
  int[] frequencySort(int[] nums) {
    int[] cnt = new int[201];
    List<Integer> t = new ArrayList<>();
    for (int v : nums) {
      v += 100;
      ++cnt[v];
      t.add(v);
    }
    t.sort((a, b)->cnt[a] == cnt[b] ? b - a : cnt[a] - cnt[b]);
    int[] ans = new int[nums.length];
    int i = 0;
    for (int v : t) {
      ans[i++] = v - 100;
    }
    return ans;
  }
}

```

### JavaScript

```javascript
/** * @param {number[]} nums * @return {number[]} */ var frequencySort =
  function (nums) {
    const m = new Map();
    for (let i = 0; i < nums.length; i++) {
      m.set(nums[i], (m.get(nums[i]) || 0) + 1);
    }
    nums.sort((a, b) => (m.get(a) != m.get(b) ? m.get(a) - m.get(b) : b - a));
    return nums;
  };

```

### CPP

```cpp
class Solution {
public:
  vector<int> frequencySort(vector<int> &nums) {
    vector<int> cnt(201);
    for (int v : nums) {
      ++cnt[v + 100];
    }
    sort(nums.begin(), nums.end(), [&](const int a, const int b) {
      if (cnt[a + 100] == cnt[b + 100])
        return a > b;
      return cnt[a + 100] < cnt[b + 100];
    });
    return nums;
  }
};

```

### Python

```python
class Solution:
    def frequencySort(self, nums: List[int]) -> List[int]: cnt = Counter(nums) return sorted(nums, key=lambda x: (cnt[x], - x))

```