#1636
Sort Array by Increasing Frequency
Easy Custom comparator
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Sort numbers by how often they appear (rarest first). When two values are equally frequent, put the larger value first.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: sort by how often each value appears; ties go bigger value first.
Why this works: count with a map, then sort with a two-key comparator.
Example: [2, 3, 1, 3, 2]
freq: 1→1, 2→2, 3→21 first, then 3, 3 before 2, 2 (tie → bigger first)[1, 3, 3, 2, 2]
✦Hints open one at a time
Count frequencies with a HashMap.
Sort an Integer[] with a comparator: frequency ascending, then value descending.
↗Approach
Box the ints, sort with Arrays.sort and a two-key comparator, then unbox.
</>Solution (Java)
import java.util.*;
class Solution {
public int[] frequencySort(int[] nums) {
Map<Integer, Integer> freq = new HashMap<>();
for (int x : nums) freq.merge(x, 1, Integer::sum);
Integer[] boxed = new Integer[nums.length];
for (int i = 0; i < nums.length; i++) boxed[i] = nums[i];
Arrays.sort(boxed, (a, b) -> {
int fa = freq.get(a), fb = freq.get(b);
if (fa != fb) return Integer.compare(fa, fb); // rarer first
return Integer.compare(b, a); // then larger value first
});
for (int i = 0; i < nums.length; i++) nums[i] = boxed[i];
return nums;
}
}!Common mistake
Trying to pass a comparator to Arrays.sort(int[]) — comparators only work on object arrays.
Complexity
- Time: O(n log n).
- Space: O(n).
Topic: Sorting
🎬 Episodes 24–28: video coming soon