Sort by Frequency

100.8k
0

An integer array arr is given. Rearrange every value in descending order of frequency.

For equal frequencies, place the smaller value first. Return the rearranged array.

Example 1

Input: arr = [5, 5, 4, 6, 4]
Output: [4, 4, 5, 5, 6]
Explanation: Values 4 and 5 appear 2 times each. Smaller value 4 comes before 5, while value 6 comes last with frequency 1.

Example 2

Input: arr = [3, -1, 3, -1, 2]
Output: [-1, -1, 3, 3, 2]
Explanation: Values -1 and 3 share frequency 2, so smaller value -1 comes first. Value 2 appears once and comes last.

Brute Force Approach

A frequency map removes repeated counting and makes every occurrence count available in constant average time. A direct next step is to sort all n array positions with frequency as the main key and numeric value as the tie-breaker.

The idea is simple, but every repeated copy still participates in comparison sorting. An element occurring many times therefore causes the same frequency decision to be compared again for several identical copies.

Algorithm

  • Begin with a frequency map built from every array value, so each comparison can read a saved count instead of scanning the array again.

  • Copy arr into answer, because comparison sorting needs a modifiable sequence while the original input remains available.

  • Sort every position in answer with frequency as the primary key, so larger occurrence counts move toward the beginning.

  • Compare numeric values after an equal-frequency result, because the smaller value must win every tie in the selected variant.

  • Treat equal values as equivalent inside the comparator, so the sorting rule remains valid for repeated copies.

  • Keep all identical values together naturally, because equal values receive the same frequency and numeric keys.

  • Return answer after sorting finishes, because every adjacent pair now follows the required priority.

Dry Run

Sort By Frequency Brute Force

Sort By Frequency Brute Force

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Sorts all values with a frequency comparator.
vector<int> sortByFrequency(vector<int>& arr) {
unordered_map<int, int> frequency;
// Each value contributes once to the frequency map.
for (int value : arr) {
frequency[value]++;
}
vector<int> answer = arr;
// Frequency decides the primary ordering.
sort(answer.begin(), answer.end(), [&](int first, int second) {
// Equal frequencies need the smaller value first.
if (frequency[first] == frequency[second]) {
return first < second;
}
// Larger frequency receives higher priority.
return frequency[first] > frequency[second];
});
return answer;
}
};
// Driver code
int main() {
vector<int> arr = {5, 5, 4, 6, 4};
Solution obj;
vector<int> answer = obj.sortByFrequency(arr);
for (int value : answer) {
cout << value << " ";
}
cout << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N log N), where N is the total number of elements/occurrences being processed. Average O(1) hash-map lookups support comparison sorting across all N occurrences.

Space Complexity: O(N + k), the returned array, frequency map for k distinct values, and language sorting storage use linear space.

Better Approach

The brute force approach sorts repeated copies separately. A useful improvement is to sort only the k distinct values and expand every value after the final distinct-value order is known.

Numeric sorting first places distinct values in increasing order. Stable sorting by frequency next moves larger counts forward without disturbing equal-frequency values, so the earlier numeric order becomes the required tie-breaker.

Algorithm

  • Begin with a frequency map built in one pass, so every distinct value keeps a single saved occurrence count.

  • Collect the k map keys into values, because only distinct values need an ordering decision.

  • Sort values in increasing numeric order, so every equal-frequency tie starts in the required smaller-value order.

  • Apply stable sorting with descending frequency as the only key, so larger counts move forward while numeric tie order stays unchanged.

  • Create an empty answer sequence, because sorted distinct values still need expansion into all n occurrences.

  • Append each value exactly frequency[value] times, so every group receives the saved size without another comparison.

  • Return answer after all distinct groups are expanded, because frequency order and numeric tie order are both preserved.

Dry Run

sort-by-frequency-better-approach

sort-by-frequency-better-approach

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Stably sorts distinct values by saved frequency.
vector<int> sortByFrequency(vector<int>& arr) {
unordered_map<int, int> frequency;
// Each value contributes once to the frequency map.
for (int value : arr) {
frequency[value]++;
}
vector<int> values;
// Only distinct values need sorting decisions.
for (auto entry : frequency) {
values.push_back(entry.first);
}
// Numeric order prepares the required tie order.
sort(values.begin(), values.end());
// Stability preserves numeric order for equal counts.
stable_sort(values.begin(), values.end(),
[&](int first, int second) {
return frequency[first] > frequency[second];
});
vector<int> answer;
// Each distinct value expands to the saved count.
for (int value : values) {
for (int count = 0; count < frequency[value]; count++) {
answer.push_back(value);
}
}
return answer;
}
};
// Driver code
int main() {
vector<int> arr = {5, 5, 4, 6, 4};
Solution obj;
vector<int> answer = obj.sortByFrequency(arr);
for (int value : answer) {
cout << value << " ";
}
cout << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N + k log k), frequency counting and expansion process N values, while two sorting passes order only k distinct values.

Space Complexity: O(N + k), the returned array, frequency map, distinct-value list, and stable sorting storage use linear space.

Optimal Approach

Stable sorting still compares frequencies among the distinct values. Every frequency lies between 1 and n, so a count can serve as a bucket index and remove comparison sorting from the frequency dimension.

Distinct values are first sorted numerically and then placed into frequency buckets in numeric order. Reading buckets from n down to 1 gives descending frequency, while insertion order inside every bucket gives the smaller-value tie-breaker.

Unrestricted integers still require numeric sorting for the tie rule. Bucket sorting removes all frequency comparisons and keeps the best comparison-based bound of O(n + k log k) for the selected variant.

Algorithm

  • Begin with a frequency map built from arr, so every distinct value has one count between 1 and n.

  • Collect all distinct values and sort the collection numerically, because later bucket insertion must preserve the smaller-value tie order.

  • Create n + 1 buckets indexed by frequency, so every possible count has a direct destination without frequency comparisons.

  • Insert each numerically ordered distinct value into buckets[frequency[value]], so equal-frequency values enter the same bucket in increasing order.

  • Scan bucket indices from n down to 1, because descending indices exactly match descending occurrence counts.

  • Append every bucket value as many times as the bucket index, so each distinct group regains the complete saved frequency.

  • Return the completed answer after the bucket scan, because both ordering rules are encoded by scan direction and insertion order.

Dry Run

sort-by-frequency-optimal-approach

sort-by-frequency-optimal-approach

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Groups distinct values inside frequency buckets.
vector<int> sortByFrequency(vector<int>& arr) {
int n = arr.size();
unordered_map<int, int> frequency;
// Each value contributes once to the frequency map.
for (int value : arr) {
frequency[value]++;
}
vector<int> values;
// Only distinct values need numeric tie ordering.
for (auto entry : frequency) {
values.push_back(entry.first);
}
// Numeric order prepares each bucket tie order.
sort(values.begin(), values.end());
vector<vector<int>> buckets(n + 1);
// Frequency selects a direct bucket destination.
for (int value : values) {
int count = frequency[value];
buckets[count].push_back(value);
}
vector<int> answer;
// Descending buckets produce larger counts first.
for (int count = n; count >= 1; count--) {
// Bucket order already resolves numeric ties.
for (int value : buckets[count]) {
for (int copy = 0; copy < count; copy++) {
answer.push_back(value);
}
}
}
return answer;
}
};
// Driver code
int main() {
vector<int> arr = {5, 5, 4, 6, 4};
Solution obj;
vector<int> answer = obj.sortByFrequency(arr);
for (int value : answer) {
cout << value << " ";
}
cout << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N + k log k), frequency counting, bucket placement, and reconstruction are linear, while numeric tie ordering sorts k distinct values.

Space Complexity: O(N + k), frequency buckets, the map, distinct values, and the returned array together use linear space.

Interview follow-up Questions

Only a different problem variant preserves input order. The selected variant places the smaller numeric value first, regardless of original position.

Sorting

Read Similar Blogs

SortingBinary Search TreeData StructuresRecursion

Search in a Binary Search Tree

In the Search in a Binary Search Tree problem, you are given the root node of a binary search tree and an integer target value. Your task is to find the specific node in the tree where the node val...

70.6k
ArraysStringHashingSorting

Group Anagrams

Input: strs = ["eat", "tea", "tan", "ate", "nat", "bat"] Output: [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]] Explanation: "eat" , "tea" , and "ate" contain one 'a' , one 'e' , and one 't' . "t...

59k
Two PointerBinary SearchMathsSortingArrays

Median of 2 Sorted Arrays

Given two sorted arrays nums1 and nums2 of size M and N respectively, return the median of the two sorted arrays. The final array is formed by merging both arrays and sorting them in non-decreasing...

79.5k
Comments0