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.
1import java.util.*;
2
3class Solution {
4 public int[] frequencySort(int[] nums) {
5 Map<Integer, Integer> freq = new HashMap<>();
6 for (int n : nums) {
7 freq.put(n, freq.getOrDefault(n, 0) + 1);
8 }
9 return Arrays.stream(nums)
10 .boxed()
11 .sorted((a, b) -> freq.get(a) != freq.get(b) ? freq.get(a) - freq.get(b) : b - a)
12 .mapToInt(Integer::intValue)
13 .toArray();
14 }
15
16 public static void main(String[] args) {
17 Solution solution = new Solution();
18 int[] nums = {1, 1, 2, 2, 2, 3};
19 System.out.println(Arrays.toString(solution.frequencySort(nums))); // Output: [3, 1, 1, 2, 2, 2]
20 }
21}This solution uses a HashMap to store the frequency of each number. It then converts the array to a stream of Integers, sorts it using a custom comparator, and finally converts it back to an array. The comparator prioritizes frequency and, in case of ties, the value itself in decreasing order.
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.
1function frequencySort(nums) {
2
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 JavaScript solution operates similarly to the described C++ solution, using an object to track the frequency of numbers and a bucket to group numbers by frequency. It sorts numbers within each bucket in descending order before constructing the final result array.