Sort Array by Increasing Frequency
EasyPrompt
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] <= 100
Approaches
4 approaches with complexity analysis and trade-offs.
This approach involves sorting the array using a custom comparator. The key idea is that for any two elements being compared during the sort, their frequencies are calculated on the fly by iterating through the entire array. This is highly inefficient as frequency counting is repeated many times, making it a brute-force method.
Algorithm
- Convert the primitive
int[]array to anInteger[]array to useArrays.sortwith a custom comparator. * Define a customComparatorthat takes two numbers,aandb. * Inside the comparator, calculate the frequency ofaby iterating through the entire array. * Similarly, calculate the frequency ofb. * Compare the frequencies. Iffreq(a)is not equal tofreq(b), returnfreq(a) - freq(b). * If the frequencies are equal, sort by value in descending order by returningb - a. * Apply this sort to theInteger[]array. * Convert the sortedInteger[]back toint[].
Walkthrough
This method directly translates the sorting criteria into a Java Comparator. We convert the input int[] to an Integer[] to be able to use Arrays.sort with a custom comparator object. The comparator's compare method is the core of the logic. For any two numbers a and b, it performs a full scan of the original array to count occurrences of a and another full scan for b. This process is repeated for every comparison the sorting algorithm makes. While straightforward to conceptualize, its performance is very poor. java import java.util.Arrays; class Solution { public int[] frequencySort(int[] nums) { Integer[] numsObj = new Integer[nums.length]; for (int i = 0; i < nums.length; i++) { numsObj[i] = nums[i]; } Arrays.sort(numsObj, (a, b) -> { long freqA = 0; long freqB = 0; for (int num : nums) { if (num == a.intValue()) freqA++; if (num == b.intValue()) freqB++; } if (freqA != freqB) { return (int) (freqA - freqB); } else { return b - a; } }); for (int i = 0; i < nums.length; i++) { nums[i] = numsObj[i]; } return nums; } }
Complexity
Time
O(N^2 * log N). The sorting algorithm (like MergeSort used by `Arrays.sort`) performs O(N log N) comparisons. Each comparison takes O(N) time to count frequencies, leading to the overall complexity.
Space
O(N). An auxiliary array of `Integer` objects is created to facilitate custom sorting.
Trade-offs
Pros
Conceptually simple, directly implementing the comparison logic.
Cons
Extremely inefficient and will likely result in a 'Time Limit Exceeded' error on most platforms for non-trivial input sizes.
A much more efficient approach is to pre-calculate the frequencies of all numbers and store them in a HashMap. This avoids the expensive re-computation of frequencies inside the sort's comparator. We first iterate through the array once to populate the frequency map. Then, we sort the array using a custom comparator that looks up frequencies from this map in constant time on average.
Algorithm
- Create a
HashMap<Integer, Integer>to store the frequency of each number. * Iterate through the input arraynumsand populate the map. * Convert theint[]toInteger[]to allow sorting with a custom object comparator. * Sort theInteger[]array usingArrays.sort()with a customComparator. * The comparator logic for two numbersaandbis: * Get their frequencies from the HashMap. * If frequencies differ, return the difference to sort by frequency (increasing). * If frequencies are equal, returnb - ato sort by value (decreasing). * Convert the sortedInteger[]back toint[].
Walkthrough
The main bottleneck of the previous approach was re-calculating frequencies. We can optimize this by computing all frequencies in a single pass and storing them. A HashMap is a suitable data structure for this, mapping each number to its count. After populating the map, we can sort the array (again, as an Integer[]) with a custom comparator. This comparator now performs a quick O(1) average time lookup in the map to get the frequencies, making the entire sorting process much faster. java import java.util.*; class Solution { public int[] frequencySort(int[] nums) { Map<Integer, Integer> freqMap = new HashMap<>(); for (int num : nums) { freqMap.put(num, freqMap.getOrDefault(num, 0) + 1); } Integer[] numsObj = new Integer[nums.length]; for (int i = 0; i < nums.length; i++) { numsObj[i] = nums[i]; } Arrays.sort(numsObj, (a, b) -> { int freqA = freqMap.get(a); int freqB = freqMap.get(b); if (freqA != freqB) { return freqA - freqB; } else { return b - a; } }); for (int i = 0; i < nums.length; i++) { nums[i] = numsObj[i]; } return nums; } }
Complexity
Time
O(N log N). It takes O(N) to build the frequency map and O(N log N) to sort the array. Map lookups inside the comparator are O(1) on average.
Space
O(N). The HashMap can store up to N unique elements, and an auxiliary `Integer[]` of size N is used for sorting.
Trade-offs
Pros
A standard and well-understood solution.
Significantly more efficient than the brute-force method.
Cons
Involves overhead from using a HashMap and boxing integers.
Not the most optimal solution in terms of time complexity.
This approach is an optimization of the HashMap method, made possible by the problem's constraint on the range of input values (-100 to 100). Instead of a HashMap, we use a simple array as a frequency map. This provides faster, guaranteed constant-time lookups without the overhead of hashing, making it slightly more performant in practice.
Algorithm
- Create an integer array
frequencyof size 201, using an offset of 100 to map values to indices (index = value + 100). * Iterate throughnumsand populate thefrequencyarray. * ConvertnumstoInteger[]. * Sort theInteger[]with a customComparatorthat uses thefrequencyarray for lookups. * The comparison logic remains the same: sort by frequency (increasing), then by value (decreasing). * Convert the sortedInteger[]back toint[].
Walkthrough
Given that nums[i] is between -100 and 100, there are only 201 possible distinct values. We can exploit this by using a fixed-size array instead of a HashMap to store frequencies. We map each number num to an index num + 100. This eliminates the overhead associated with hashing and potential collisions in a HashMap, resulting in faster and more consistent performance for frequency lookups. The rest of the logic, involving sorting a temporary Integer[] array, remains the same as the previous approach. java import java.util.Arrays; import java.util.Comparator; class Solution { public int[] frequencySort(int[] nums) { int[] freq = new int[201]; for (int num : nums) { freq[num + 100]++; } Integer[] numsObj = new Integer[nums.length]; for (int i = 0; i < nums.length; i++) { numsObj[i] = nums[i]; } Arrays.sort(numsObj, (a, b) -> { int freqA = freq[a + 100]; int freqB = freq[b + 100]; if (freqA != freqB) { return freqA - freqB; } else { return b - a; } }); for (int i = 0; i < nums.length; i++) { nums[i] = numsObj[i]; } return nums; } }
Complexity
Time
O(N log N). O(N) to build the frequency array and O(N log N) for sorting. Array lookups are O(1).
Space
O(N). O(K) for the frequency array where K is the range of values (201, which is constant space O(1)), and O(N) for the `Integer[]` copy.
Trade-offs
Pros
More efficient than the HashMap approach due to faster array lookups.
Constant space for frequency counting.
Cons
Relies on the constraint of a small range of input values.
Still bottlenecked by the O(N log N) comparison sort.
The most efficient approach avoids a comparison-based sort, achieving linear time complexity. It uses a 'bucket sort' style algorithm. After counting frequencies, we create 'buckets' for each possible frequency (from 1 to N). Each bucket holds the numbers that appear with that frequency. We then build the result array by iterating through the buckets in order of increasing frequency.
Algorithm
- Count frequencies of each number using a frequency array (size 201). * Create an array of lists (buckets), where
buckets[f]will store numbers with frequencyf. The array size isN + 1. * Iterate through the possible numbers (-100 to 100). For each number with frequencyf > 0, add it tobuckets[f]. To handle the tie-breaking rule (decreasing value), iterate numbers from 100 down to -100. * Initialize an empty result array. * Iterate through the buckets from frequencyf = 1toN. * For each numbernuminbuckets[f], appendnumto the result arrayftimes.
Walkthrough
This approach achieves optimal O(N) time complexity by avoiding a comparison-based sort. 1. Frequency Counting: First, we count frequencies using an array, just like in the previous approach. 2. Bucketing: We create an array of lists, where the index represents a frequency. buckets[f] will hold all numbers that appear f times. We iterate through our frequency map. If a number num has frequency f, we add num to buckets[f]. To satisfy the secondary sorting condition (decreasing value for same frequency), we can populate the buckets by iterating through the numbers from highest to lowest (100 down to -100). This ensures that for any given frequency, the numbers are added to the bucket in decreasing order automatically. 3. Building the Result: Finally, we iterate through the buckets from frequency 1 up to the maximum possible frequency. For each frequency, we take the numbers from its bucket and append them to our result array the required number of times. java import java.util.*; class Solution { public int[] frequencySort(int[] nums) { int[] freq = new int[201]; for (int num : nums) { freq[num + 100]++; } List<Integer>[] buckets = new List[nums.length + 1]; for (int i = 0; i < buckets.length; i++) { buckets[i] = new ArrayList<>(); } for (int i = 200; i >= 0; i--) { if (freq[i] > 0) { int num = i - 100; buckets[freq[i]].add(num); } } int[] result = new int[nums.length]; int index = 0; for (int f = 1; f <= nums.length; f++) { for (int num : buckets[f]) { for (int i = 0; i < f; i++) { result[index++] = num; } } } return result; } }
Complexity
Time
O(N). O(N) to count frequencies, O(K) to populate buckets (where K=201 is constant), and O(N) to build the final array. The total complexity is O(N + K), which simplifies to O(N).
Space
O(N). O(K) for the frequency array, O(N) for the buckets (as the total number of items across all buckets is the number of unique elements, at most N), and O(N) for the result array.
Trade-offs
Pros
Optimal linear time complexity.
Efficiently handles all sorting criteria without a comparison sort.
Cons
More complex to implement compared to sorting-based solutions.
Uses more auxiliary space for the buckets.
Solutions
Solution
class Solution {public int[] frequencySort(int[] nums) { int[] cnt = new int[201]; List<Integer> t = new ArrayList<>(); for (int v : nums) { v += 100; ++cnt[v]; t.add(v); } t.sort((a, b)->cnt[a] == cnt[b] ? b - a : cnt[a] - cnt[b]); int[] ans = new int[nums.length]; int i = 0; for (int v : t) { ans[i++] = v - 100; } return ans; }}/** * @param {number[]} nums * @return {number[]} */ var frequencySort = function (nums) { const m = new Map(); for (let i = 0; i < nums.length; i++) { m.set(nums[i], (m.get(nums[i]) || 0) + 1); } nums.sort((a, b) => (m.get(a) != m.get(b) ? m.get(a) - m.get(b) : b - a)); return nums; };class Solution {public: vector<int> frequencySort(vector<int> &nums) { vector<int> cnt(201); for (int v : nums) { ++cnt[v + 100]; } sort(nums.begin(), nums.end(), [&](const int a, const int b) { if (cnt[a + 100] == cnt[b + 100]) return a > b; return cnt[a + 100] < cnt[b + 100]; }); return nums; }};class Solution: def frequencySort(self, nums: List[int]) -> List[int]: cnt = Counter(nums) return sorted(nums, key=lambda x: (cnt[x], - x))Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.