Sort Array by Increasing Frequency - Solution & Explanation
Problem Statement
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
Approach Overview
Problem 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.
Approach 1: Frequency Map and Sort
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.
Complexity
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.
Approach 2: Bucket Sort Based on Frequency
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.
Code
C++
JavaScript
Complexity
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.
Approach 3: Default Approach
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
Complexity Comparison
| 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 | — |
Detailed Complexity Analysis
| 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. |
Video Solution
Leetcode 1636 Sort Array by Increasing Frequency • Fraz • 19,619 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Sort Array by Increasing Frequency easy or hard?
Sort Array by Increasing Frequency Python/Java solution
How to solve Sort Array by Increasing Frequency in O(n)?
What is the best approach for Sort Array by Increasing Frequency?
Is Sort Array by Increasing Frequency asked at Google/Amazon/Meta?
What data structure is used in Sort Array by Increasing Frequency?
What is the time complexity of Sort Array by Increasing Frequency?
Ready to solve this problem?
Practice Sort Array by Increasing Frequency with our built-in code editor and test cases.
Practice on FleetCode