Sort Array by Increasing Frequency — Problem & Solution
Sort Array by Increasing Frequency solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Sort Array by Increasing Frequency is an easy coding problem on arrays, hash table and sorting, asked in Amazon and Adobe interviews.
- Difficulty: Easy
- Topics: Arrays, Hash Table, Sorting
- Asked at: Amazon, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an array of integers nums, sort it in increasing order of the frequency of the values.
Values that occur equally often are sorted in decreasing order of value.
Example 1
Input: nums = [1,1,2,2,2,3]
Output: [3,1,1,2,2,2]
Explanation: 3 occurs once, 1 twice, 2 three times.
Example 2
Input: nums = [2,3,1,3,2]
Output: [1,3,3,2,2]
Explanation: 2 and 3 both occur twice, so the larger value comes first.
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 <= 40-100 <= nums[i] <= 100
Hints for Sort Array by Increasing Frequency
Hint 1
Count the occurrences first, then sort with a comparator that reads those counts.
Hint 2
The primary key is the count ascending; the secondary key is the value descending.
Hint 3
Sorting the original array (not the distinct values) keeps every copy in the output.
How to solve Sort Array by Increasing Frequency
Count occurrences, then sort the original array by (count ascending, value descending).
Approach
- Count each value.
- Sort
numswith key(count[x], -x).
Why it works
Sorting the array itself keeps every copy, and the composite key encodes both rules.
Complexity
- Time —
O(n log n) - Space —
O(n)
Pitfalls
- Sorting the distinct values and expanding also works but is more bookkeeping.
Reference solution
Python
def frequencySort(nums):
count = {}
for x in nums:
count[x] = count.get(x, 0) + 1
return sorted(nums, key=lambda x: (count[x], -x))Java
public static int[] frequencySort(int[] nums) {
Map<Integer, Integer> count = new HashMap<>();
for (int x : nums) count.put(x, count.getOrDefault(x, 0) + 1);
Integer[] boxed = new Integer[nums.length];
for (int i = 0; i < nums.length; i++) boxed[i] = nums[i];
Arrays.sort(boxed, (a, b) -> {
int ca = count.get(a), cb = count.get(b);
if (ca != cb) return ca - cb;
return b - a;
});
int[] out = new int[nums.length];
for (int i = 0; i < nums.length; i++) out[i] = boxed[i];
return out;
}C++
vector<int> frequencySort(vector<int>& nums) {
unordered_map<int, int> count;
for (int x : nums) count[x]++;
vector<int> out = nums;
sort(out.begin(), out.end(), [&](int a, int b) {
int ca = count[a], cb = count[b];
if (ca != cb) return ca < cb;
return a > b;
});
return out;
}JavaScript
var frequencySort = function(nums) {
const count = new Map();
for (let i = 0; i < nums.length; i++) {
count.set(nums[i], (count.get(nums[i]) || 0) + 1);
}
return nums.slice().sort(function(a, b) {
const ca = count.get(a), cb = count.get(b);
if (ca !== cb) return ca - cb;
return b - a;
});
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets