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

🧠 Problem Idea

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

Example:

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

Approach 1: unordered_map + sorting (What I tried first)

Code

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
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 < p.second; i++)
            res.push_back(p.first);
    }

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

⏱ Time Complexity

Counting: O(n)

Sorting k unique elements: O(k log k)

Building result: O(n)

👉 Total: O(n + k log k)

💾 Space Complexity (why NOT 2k)

unordered_map → O(k)

vector → O(k)

res → O(n)

👉 Total: O(n + k)

✅ We don’t write 2k because in Big-O:

O(k + k) = O(k)

Constants are ignored.

Can we solve this without sorting? ✅ YES — Bucket Method

This avoids k log k sorting completely.

🔹Bucket Sort by Frequency (Fixed Vector Frequency)

Core Idea

1. Count frequency
2. Store numbers in buckets where index = frequency
3. Traverse buckets from high → low

Step-by-step Visualization

For input:

[1,1,2,2,2,3]

Frequency Map

1 → 2
2 → 3
3 → 1

• Buckets (index = frequency)

bucket[1] → [3]
bucket[2] → [1]
bucket[3] → [2]

• Traversal Start from highest frequency:

bucket[3] → 2 2 2
bucket[2] → 1 1
bucket[1] → 3

Bucket-Based C++ Code (No Sorting)

#include <iostream>
#include <vector>
using namespace std;

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

    const int MAX = 100;          // value range
    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 < MAX; 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 (Bucket Method)
Time

Frequency count → O(n)

Bucket traversal → O(n)

👉 Total: O(n)
(No sorting!)

Space

Frequency array → O(k)

Buckets → O(k)

Result → O(n)

👉 Total: O(n + k)

🧠 What I Learned

1. Sorting is not always required
2. Bucket storage converts sorting into indexing
3. Constant factors are ignored in Big-O

O(2k) → O(k)

4.unordered_map is flexible

Note : Fixed frequency arrays are faster when range is known

💡Practice Challenge

Try solving this again using unordered_map without sorting.
Can you adapt the bucket idea yourself?