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.
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; }}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.