Sort Array by Increasing Frequency
Problem
Given an integer array, sort it in increasing order based on the frequency of values. If multiple values have the same frequency, sort them in decreasing order.
nums = [1,1,2,2,2,3][3,1,1,2,2,2]from collections import Counter
def frequency_sort(nums):
c = Counter(nums)
return sorted(nums, key=lambda x: (c[x], -x))function frequencySort(nums) {
const c = new Map();
for (const x of nums) c.set(x, (c.get(x) || 0) + 1);
return nums.slice().sort((a, b) => c.get(a) - c.get(b) || b - a);
}class Solution {
public int[] frequencySort(int[] nums) {
Map<Integer, Integer> c = new HashMap<>();
for (int x : nums) c.merge(x, 1, Integer::sum);
return Arrays.stream(nums).boxed()
.sorted((a, b) -> c.get(a) != c.get(b) ? c.get(a) - c.get(b) : b - a)
.mapToInt(Integer::intValue).toArray();
}
}vector<int> frequencySort(vector<int>& nums) {
unordered_map<int,int> c;
for (int x : nums) c[x]++;
sort(nums.begin(), nums.end(), [&](int a, int b) {
return c[a] != c[b] ? c[a] < c[b] : a > b;
});
return nums;
}Explanation
We must reorder the numbers so the rarest values come first, and when two values are equally rare, the larger value comes first. The two-step plan is: count how often each value appears, then sort with a custom rule.
First we build a frequency map c using a Counter, so c[x] tells us how many times x occurs in the array.
Then we sort with the key (c[x], -x). Sorting compares the first part first: smaller frequency wins, giving ascending frequency. The second part -x breaks ties by putting the bigger number first (because a more-negative key sorts earlier).
Example: nums = [1,1,2,2,2,3]. Counts are 3→1, 1→2, 2→3. Sorting by frequency puts the single 3 first, then both 1's, then all three 2's, giving [3,1,1,2,2,2].