Given an array of integers nums, sort the array in increasing order based on the frequency of the values. If multiple values have the same frequency, sort them in decreasing order.
Return the sorted array.
Example 1:
Input: nums = [1,1,2,2,2,3] Output: [3,1,1,2,2,2] Explanation: '3' has a frequency of 1, '1' has a frequency of 2, and '2' has a frequency of 3.
Example 2:
Input: nums = [2,3,1,3,2] Output: [1,3,3,2,2] Explanation: '2' and '3' both have a frequency of 2, so they are sorted in decreasing order.
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 <= 100-100 <= nums[i] <= 100To solve #1636 Sort Array by Increasing Frequency, the key idea is to first understand how often each number appears and then order the elements based on that frequency. A common strategy is to use a hash map to count the occurrences of each value in the array. This allows quick lookup of how many times each number appears.
Once the frequencies are known, apply a custom sorting rule. The array should be sorted by increasing frequency, meaning numbers that appear fewer times come first. If two numbers share the same frequency, the one with the larger value should come earlier. Many programming languages allow sorting with a custom comparator that uses the frequency map during comparisons.
This approach works efficiently because counting frequencies takes O(n) time, and sorting the array based on the defined criteria typically takes O(n log n). The hash map introduces additional memory usage but keeps the overall solution simple and efficient.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Hash Map + Custom Sorting | O(n log n) | O(n) |
Fraz
Use these hints if you're stuck. Try solving on your own first.
Count the frequency of each value.
Use a custom comparator to compare values by their frequency. If two values have the same frequency, compare their values.
This approach involves creating a frequency map for all the numbers in the array. Then, sort the numbers based on their frequency, with a secondary sort order for numbers with the same frequency in decreasing numeric order.
Time Complexity: O(N log N), where N is the number of elements in nums, due to sorting.
Space Complexity: O(N), for storing the frequency map.
1from collections import Counter
2
3def frequencySort(nums):
4 freq = Counter(nums)
5 return sorted(nums, key=lambda x: (freq[x], -x))
6
7# Example usage:
8nums = [1, 1, 2, 2, 2, 3]
9print(frequencySort(nums)) # Output: [3, 1, 1, 2, 2, 2]The solution uses the Counter from the collections module to count the frequency of each number in nums. Then, it sorts the numbers using a custom key: the primary key is the frequency, and the secondary key is the negative of the number to ensure decreasing order when frequencies match.
This approach uses a bucket sort strategy by grouping numbers into buckets based on their frequencies, then sorting within each bucket based on the requirement of decreasing order for equal frequency numbers.
Time Complexity: O(N + K log K), where N is the number of elements and K is the number of distinct elements, due to bucket sorting and sorting each bucket.
Space Complexity: O(N + K), for buckets and frequency storage.
1#include <vector>
2#include <unordered_map>
3#include <algorithm>
4#include <iostream>
5using namespace std;
vector<int> frequencySort(vector<int>& nums) {
unordered_map<int, int> freq;
int maxFreq = 0;
for (int num : nums) {
freq[num]++;
maxFreq = max(maxFreq, freq[num]);
}
vector<vector<int>> buckets(maxFreq + 1);
for (auto& [num, count] : freq) {
buckets[count].push_back(num);
}
vector<int> result;
for (int i = 1; i <= maxFreq; ++i) {
sort(buckets[i].rbegin(), buckets[i].rend());
for (int num : buckets[i]) {
result.insert(result.end(), i, num);
}
}
return result;
}
int main() {
vector<int> nums = {1, 1, 2, 2, 2, 3};
vector<int> sorted = frequencySort(nums);
for (int num : sorted) {
cout << num << " ";
}
// Output: 3 1 1 2 2 2
return 0;
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
The problem specifies that when two elements have the same frequency, the larger number should appear first. Therefore, the sorting rule uses increasing frequency but decreasing value as a tiebreaker. This ensures the output matches the required ordering.
Yes, this type of problem is common in coding interviews because it combines frequency counting with custom sorting. It tests understanding of hash maps, comparator logic, and time complexity analysis, which are core DSA concepts.
A hash table (or hash map) is the most suitable data structure because it allows efficient counting of element frequencies. It provides constant-time average lookups, which makes building the frequency map fast and practical for sorting decisions.
The optimal approach uses a hash map to count the frequency of each number and then sorts the array with a custom comparator. The comparator prioritizes lower frequencies first and, for equal frequencies, higher numeric values. This keeps the logic simple and runs in O(n log n) time.
This approach constructs frequency buckets, where each index in the bucket corresponds to the frequency of numbers. Each bucket contains numbers with identical frequencies. For each frequency bucket, we sort numbers in decreasing order, fulfilling the condition of the problem, and append them to the result.