Medium · bucket counting

Counting Sort

You sorted with bubble sort by comparing pairs. This one never compares anything — and that's not a trick, it's a different trade: memory and a known value range in exchange for speed.

At a glanceEvery value is between 0 and 100, so count occurrences in a 101-slot array and print the values back in order — O(n + 101) instead of O(n log n).

Problem

Input: The first line is an integer n (1 ≤ n ≤ 1000). The second line holds n integers separated by spaces, each between 0 and 100 inclusive.

Output: The same numbers in non-decreasing order, separated by single spaces.

Samples:

Input	Output
`5 5 3 8 1 9`	`1 3 5 8 9`
`4 7 7 2 2`	`2 2 7 7`
`3 0 100 50`	`0 50 100`

The value range 0–100 is not a detail, it's the precondition. Counting sort only works because you can afford one counter per possible value. With values up to a billion it would need a billion counters.

Your solution

main.cpp — your solution

Custom input for "Run my input"

Judging runs in your browser against hidden tests. A runaway loop is cut off after 3 seconds — still, make sure every loop has an exit. Your code is saved in this browser as you type.

Stuck? Hints

Hint 1 — You've already used a counting array

Digit Frequency did exactly this: an array where the index is the value and the element is how many times it occurred. Sorting is just reading that array out from left to right.

Hint 2 — Two nested loops, neither one comparing

Outer loop v from 0 to 100. Inner loop runs cnt[v] times, printing v each time. If a value appeared four times, you print it four times. If it never appeared, the inner loop runs zero times — no if needed.

Hint 3 — The bug that looks right on distinct values

Printing each value once (ignoring its count) gives a perfect answer whenever all inputs are different — so it passes the first sample and fails the moment anything repeats. Test with 7 7 2 2 before you trust your code.

Solution (try it first!)

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int cnt[101] = {0};

    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        cnt[x]++;
    }

    for (int v = 0; v <= 100; v++) {
        for (int k = 0; k < cnt[v]; k++) cout << v << " ";
    }
    cout << endl;
    return 0;
}

Counting sort is O(n + k) where k is the value range — faster than any comparison sort, which cannot beat O(n log n). That's not a violation of the lower bound: the bound only applies to algorithms that learn about the data through comparisons. Here you learn through the values themselves. Real systems use this everywhere: sorting ages, scores, pixel values, or bytes. Next, the first genuinely recursive problem in the set — Tower of Hanoi.

Deep dive

Why this works

Make the index the value and the element the number of occurrences; sorting then becomes reading that array left to right.

The cost

O(n + k) with k the value range. Faster than any comparison sort — because the O(n log n) lower bound only constrains algorithms that learn about the data *through comparisons*, and you learn through the values themselves.

Where it goes wrong

Printing each value once and ignoring its count is perfectly correct when all inputs differ — and fails the moment anything repeats.
Forgetting to zero the counter array (int cnt[101] = {0};) accumulates on top of whatever garbage was there.

Next step

The first genuinely recursive problem here: Tower of Hanoi.

Two things to remember

Index is the value, element is the count — sorting becomes reading.
It's fast because the value range is small. That's a precondition, not a detail.

🐞 This version fails — open it and try

Prints each value once — correct only when nothing repeats

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int cnt[101] = {0};

    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        cnt[x]++;
    }

    for (int v = 0; v <= 100; v++) {
        if (cnt[v] > 0) cout << v << " ";
    }
    cout << endl;
    return 0;
}