Code Logo

Sort Array by Increasing Frequency

Published at24 Jul 2026
Created by
Easy 0 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
Recommendation Algorithm Flow for Sort Array by Increasing Frequency

Solution Approach

Count frequencies, then sort with custom comparator.

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

Time O(n log n), Space O(n).

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();
    }
}