Sorting Elements by Frequency in C++ (Map vs Bucket Approach)

Source: Dev.to

Problem Idea

Given an array, sort the elements by descending frequency and rebuild the array so that the most frequent elements appear first.

Example
Input: [1,1,2,2,2,3]
Output: [2,2,2,1,1,3]

Approach 1: unordered_map + Sorting

Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v = {1,1,2,2,2,3};
    unordered_map<int,int> freq;
    vector<int> res;

    for (int x : v) freq[x]++;

    vector<pair<int,int>> vec(freq.begin(), freq.end());

    sort(vec.begin(), vec.end(),
         [](auto &a, auto &b){ return a.second > b.second; });

    for (auto &p : vec) {
        for (int i = 0; i 

Time & Space Complexity

• Frequency count: O(n)
• Sorting: O(m log m) where m is the number of distinct elements
• Reconstruction: O(n)

Total time: O(n + m log m)
Space: O(m) for the map and vector of pairs.

Approach 2: Bucket (Counting Sort)

Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v = {1,1,2,2,2,3};

    const int MAX = 100;               // maximum possible value (adjust as needed)
    vector<int> freq(MAX, 0);

    for (int x : v) freq[x]++;

    int maxFreq = 0;
    for (int f : freq) maxFreq = max(maxFreq, f);

    vector<vector<int>> bucket(maxFreq + 1);
    for (int i = 0; i < (int)freq.size(); ++i) {
        if (freq[i] > 0)
            bucket[freq[i]].push_back(i);
    }

    vector<int> res;
    for (int f = maxFreq; f > 0; f--) {
        for (int val : bucket[f]) {
            for (int i = 0; i < f; i++)
                res.push_back(val);
        }
    }

    for (int x : res) cout << x << " ";
}

Time & Space Complexity

• Frequency count: O(n)
• Bucket traversal & reconstruction: O(n)

Total time: O(n)

• Frequency array: O(k)
• Buckets: O(k)
• Result vector: O(n)

Total space: O(n + k)

What I Learned

• Sorting is not always required; bucket storage can replace sorting with simple indexing.
• Constant factors are ignored in Big‑O notation (O(2k) → O(k)).
• unordered_map is flexible, but a fixed‑size frequency array is faster when the value range is known.

Practice Challenge

• Solve the problem again using only unordered_map without sorting.
• Adapt the bucket idea to work with an unordered_map‑based frequency table.