Sort Array by Increasing Frequency solution and explanation
Google
9 more videos on this problem
Leetcode 1636 Sort Array by Increasing FrequencyFraz · 4:11 · 19K views
Sort Array by Increasing Frequency - Leetcode 1636 - PythonNeetCodeIO · 8:17 · 15K views
Leetcode | 1636. Sort Array by Increasing Frequency | Easy | Java SolutionDeveloper Docs · 9:20 · 8K views
1636. Sort Array by Increasing Frequency (Leetcode Easy)Programming Live with Larry · 3:04 · 2K views
1636. Sort Array by Increasing Frequency - LeetCode JavaScriptBecoming A Better Dev (with David) · 6:54 · 851 views
Sort Array by Increasing Frequency - LeetCode 1636 - Java Solutionalgobest - Computer Science · 4:16 · 848 views
1636. Sort Array by Increasing Frequency | Leetcode | C++ - DSATechnosier · 9:31 · 681 views
Leetcode 1636. Sort Array by Increasing Frequency | తెలుగులోVarun Penumudi · 13:31 · 337 views
LeetCode 1636 - Sort Array By Increasing Frequency - JavaAlpha-Code · 8:20 · 311 views
Sort Array by Increasing Frequency - Leetcode 1636 - JavaCode With K5KC · 5:51 · 187 views
The problem
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.
from collections import Counter
def frequencySort(nums):
freq = Counter(nums)
return sorted(nums, key=lambda x: (freq[x], -x))
# Example usage:
nums = [1, 1, 2, 2, 2, 3]
print(frequencySort(nums)) # Output: [3, 1, 1, 2, 2, 2]import java.util.*;
class Solution {
public int[] frequencySort(int[] nums) {
Map<Integer, Integer> freq = new HashMap<>();
for (int n : nums) {
freq.put(n, freq.getOrDefault(n, 0) + 1);
}
return Arrays.stream(nums)
.boxed()
.sorted((a, b) -> freq.get(a) != freq.get(b) ? freq.get(a) - freq.get(b) : b - a)
.mapToInt(Integer::intValue)
.toArray();
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums = {1, 1, 2, 2, 2, 3};
System.out.println(Arrays.toString(solution.frequencySort(nums))); // Output: [3, 1, 1, 2, 2, 2]
}
}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.
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.
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <iostream>
using namespace std;
vector<int> frequencySort(vector<int>& nums) {
unordered_map<int, int> freq;
int maxFreq = 0;
for (int num : nums) {
freq[num]++;
maxFreq = max(maxFreq, freq[num]);
}
vector<vector<int>> buckets(maxFreq + 1);
for (auto& [num, count] : freq) {
buckets[count].push_back(num);
}
vector<int> result;
for (int i = 1; i <= maxFreq; ++i) {
sort(buckets[i].rbegin(), buckets[i].rend());
for (int num : buckets[i]) {
result.insert(result.end(), i, num);
}
}
return result;
}
int main() {
vector<int> nums = {1, 1, 2, 2, 2, 3};
vector<int> sorted = frequencySort(nums);
for (int num : sorted) {
cout << num << " ";
}
// Output: 3 1 1 2 2 2
return 0;
}function frequencySort(nums) {
const freq = {};
let maxFreq = 0;
nums.forEach(num => {
freq[num] = (freq[num] || 0) + 1;
maxFreq = Math.max(maxFreq, freq[num]);
});
const buckets = Array.from({length: maxFreq + 1}, () => []);
for (const [num, count] of Object.entries(freq)) {
buckets[count].push(Number(num));
}
const result = [];
for (let i = 1; i <= maxFreq; i++) {
buckets[i].sort((a, b) => b - a);
for (const num of buckets[i]) {
result.push(...Array(i).fill(num));
}
}
return result;
}
// Example usage:
const nums = [1, 1, 2, 2, 2, 3];
console.log(frequencySort(nums)); // Output: [3, 1, 1, 2, 2, 2]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.
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
function frequencySort(nums: number[]): number[] {
const map = new Map<number, number>();
for (const num of nums) {
map.set(num, (map.get(num) ?? 0) + 1);
}
return nums.sort((a, b) => map.get(a) - map.get(b) || b - a);
}func frequencySort(nums []int) []int {
cnt := make([]int, 201)
for _, v := range nums {
cnt[v+100]++
}
sort.Slice(nums, func(i, j int) bool {
a, b := nums[i]+100, nums[j]+100
return cnt[a] < cnt[b] || cnt[a] == cnt[b] && a > b
})
return nums
}use std::collections::HashMap;
impl Solution {
pub fn frequency_sort(mut nums: Vec<i32>) -> Vec<i32> {
let n = nums.len();
let mut map = HashMap::new();
for &num in nums.iter() {
*map.entry(num).or_insert(0) += 1;
}
nums.sort_by(|a, b| {
if map.get(a) == map.get(b) {
return b.cmp(a);
}
map.get(a).cmp(&map.get(b))
});
nums
}
}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 | – |
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. |
Frequently asked questions
Is Sort Array by Increasing Frequency easy or hard?
Sort Array by Increasing Frequency is categorized as an Easy problem. The main idea is counting element frequencies and applying a custom sort rule. Developers familiar with hash maps and sorting can implement the solution quickly.
Sort Array by Increasing Frequency Python/Java solution
In Python, use collections.Counter to count frequencies and sort with a key like (freq[x], -x). In Java, build a HashMap<Integer, Integer> for counts and sort the array with a custom comparator based on frequency and value. Both implementations run in O(n log n) time.
How to solve Sort Array by Increasing Frequency in O(n)?
Use bucket sort after computing frequencies with a hash map. Create buckets where index i contains numbers appearing exactly i times. Iterate buckets from lowest to highest frequency and append numbers in descending order of value. Each element is processed a constant number of times, giving O(n) time and O(n) space.
What is the best approach for Sort Array by Increasing Frequency?
The most practical approach uses a hash map to count frequencies and then sorts the array with a custom comparator. The comparator sorts by frequency in ascending order and by value in descending order when frequencies tie. This method runs in O(n log n) time due to sorting and uses O(n) space for the frequency map.
Is Sort Array by Increasing Frequency asked at Google/Amazon/Meta?
Frequency-based sorting problems appear in interviews at companies like Amazon and Google because they combine hash tables with custom sorting logic. The problem tests whether you can derive ordering rules from constraints and implement them efficiently.
What data structure is used in Sort Array by Increasing Frequency?
A hash table (hash map) is used to store the frequency of each number in the array. After counting, the array is sorted using a custom comparator or processed using bucket sort. Arrays and hash maps are the primary data structures involved.
What is the time complexity of Sort Array by Increasing Frequency?
The common solution using a frequency map followed by sorting runs in O(n log n) time. Counting frequencies takes O(n), and sorting the array dominates the complexity. A bucket sort variant can reduce the time complexity to O(n) by grouping numbers by frequency.