Code Logo

Sort Array by Increasing Frequency

Published at24 Jul 2026
Created by
Easy 2 views
Like0

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

Count frequencies with a hash map, then apply a custom comparator that sorts by frequency ascending then by value descending for ties. This is a two-step sorting approach: first aggregate frequencies, then apply custom comparison during sorting.

Time is O(n log n) dominated by sorting, space O(n) for the frequency map. Edge cases include empty array (return []), single element, and all values having the same frequency (sorted by value descending).

The comparator pattern used here is common in problems requiring custom sort orders. The key is mapping each element to its derived sort key and then applying language-specific sorting with a custom function.

For ties at the same frequency (like -1 and 4 both appearing twice), sorting by decreasing value means larger values appear first (4 before -1). This secondary sorting ensures a deterministic total order when primary sort keys are equal.

This problem is a variation of the frequency sort pattern where the sort order depends on aggregate properties of each distinct value rather than on the values themselves.

Example Input & Output

Example 1
Input
[2,3,1,3,2]
Output
[1,3,3,2,2]
Explanation

1 freq 1, 2 and 3 freq 2, 3>2.

Example 2
Input
[1,1,2,2,2,3]
Output
[3,1,1,2,2,2]
Explanation

1 freq 2, 2 freq 3, 3 freq 1.

Example 3
Input
[]
Output
[]
Explanation

Empty.

Example 4
Input
[5,-1,4,4,-1]
Output
[5,4,4,-1,-1]
Explanation

5 freq 1, -1 freq 2, 4 freq 2. Tie: 4 > -1.

Example 5
Input
[5,5,5]
Output
[5,5,5]
Explanation

All same.

Algorithm Flow

Recommendation Algorithm Flow for Sort Array by Increasing Frequency

Solution Approach

Count the frequency of each element using a hash map, then sort the array based on those frequencies in ascending order. Elements with the same frequency maintain their relative order.

function frequencySort(nums) {
  var freq = {};
  for (var i = 0; i < nums.length; i++) {
    freq[nums[i]] = (freq[nums[i]] || 0) + 1;
  }
  return nums.sort(function(a, b) {
    if (freq[a] !== freq[b]) return freq[a] - freq[b];
    return a - b;
  });
}

Build a frequency map where keys are numbers and values are their occurrence counts. Then use a custom sort comparator that first compares by frequency (ascending), and ties are broken by the number value itself (ascending).

Time complexity is O(n log n) for sorting, space complexity is O(n) for the frequency map.

Best Answers

java
import java.util.*;
class Solution {
    public int[] solution(int[] nums) {
        Map<Integer,Integer> f=new HashMap<>();
        for (int n:nums) f.put(n,f.getOrDefault(n,0)+1);
        Integer[] boxed=Arrays.stream(nums).boxed().toArray(Integer[]::new);
        Arrays.sort(boxed,(a,b)->{
            int fa=f.get(a),fb=f.get(b);
            if (fa!=fb) return fa-fb;
            return b-a;
        });
        return Arrays.stream(boxed).mapToInt(i->i).toArray();
    }
}