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] <= 100Problem Overview: Given an integer array, reorder the elements so numbers with lower frequency appear first. If two numbers have the same frequency, the larger number should come first. The output is simply the array sorted by these two rules.
Approach 1: Frequency Map and Sort (O(n log n) time, O(n) space)
The most direct solution counts how often each number appears using a hash map. After building the frequency map, sort the array using a custom comparator: first compare frequencies (ascending), and if they match, compare values (descending). Most languages allow sorting with a custom key or comparator, which makes this approach concise. The key insight is separating counting from ordering: the hash table gives O(1) lookups for frequency, while the sorting step applies the problem’s ordering rules. Overall complexity is dominated by sorting, giving O(n log n) time and O(n) extra space for the frequency map.
Approach 2: Bucket Sort Based on Frequency (O(n) time, O(n) space)
Since frequencies range from 1 to n, you can avoid comparison sorting. First count frequencies with a hash map. Then create buckets where index i stores numbers that appear exactly i times. Iterate through buckets from low frequency to high. Inside each bucket, sort numbers in descending order to satisfy the tie-breaking rule, then append each number freq times to the result. This transforms the problem into grouped processing rather than global sorting. Because each element is processed a constant number of times, the total complexity becomes O(n) time with O(n) space. This approach relies on properties of the array size and frequency bounds.
Recommended for interviews: The frequency map + sort approach is usually expected. It’s simple, readable, and easy to implement under time pressure. Interviewers mainly want to see that you identify the two sorting criteria and use a hash map to compute frequencies. Bucket sort shows deeper algorithmic thinking and improves the theoretical complexity to O(n), but it’s rarely required unless the interviewer explicitly asks for linear time.
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.
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.
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.
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.
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.
C++
JavaScript
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.
Python
Java
C++
Go
TypeScript
Rust
JavaScript
| Approach | Complexity |
|---|---|
| Frequency Map and Sort | Time Complexity: O(N log N), where N is the number of elements in Space Complexity: O(N), for storing the frequency map. |
| Bucket Sort Based on Frequency | 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. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Frequency Map and Sort | O(n log n) | O(n) | General case. Simple to implement using hash map and custom sort comparator. |
| Bucket Sort Based on Frequency | O(n) | O(n) | When frequency range is bounded by array size and you want linear-time processing. |
Leetcode 1636 Sort Array by Increasing Frequency • Fraz • 19,537 views views
Watch 9 more video solutions →Practice Sort Array by Increasing Frequency with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor