Bucket & Counting Sort

At a glance

The instinct

Comparison sorts can never beat n log n, but they also never look at what the keys are. If you know the keys are small integers - 26 letters, ages 0..150, or frequencies that cannot exceed n - you can skip comparisons entirely and use each key as an address. Drop every item into the slot its key points to, then sweep the slots in order. That single idea powers counting sort, bucket sort by frequency, and the pigeonhole trick behind Maximum Gap.

Recognise it

Not this pattern if...

• Keys are unbounded or sparse (values up to 10^9 with n = 10^5) and you need full order - use a regular sort or a hash map.
• You need the k-th largest from a stream - a heap or quickselect fits better.
• Order matters only relative to neighbours (next greater) - see monotonic stack.

Memory hack

For frequency problems, flip the map: instead of "value -> count", build "count -> list of values". The bucket index is the rank.

Say it out loud in the interview:

1. "What is the key, and what is its maximum possible value?" (frequency <= n, letter < 26).
2. "Allocate buckets indexed by that key and scatter each item into its bucket."
3. "Gather by sweeping buckets in the needed direction, stopping once I have k items."

How it works

Counting sort has three phases: count occurrences of each key, optionally turn counts into prefix sums (giving each key's final start position, which keeps the sort stable), then place items.

Bucket sort by frequency (Sort Characters By Frequency, Top K Frequent Words): first a hash map gives value -> freq; then an array buckets[freq] holds lists of values; finally walk from n down to 1.

Pigeonhole buckets (Maximum Gap): with n numbers between min and max, the largest gap is at least ceil((max - min) / (n - 1)). Make buckets that wide; any gap inside a bucket is smaller, so you only need each bucket's min and max and compare consecutive non-empty buckets.

flowchart LR
    A[Input items] --> B[Count: key -> frequency]
    B --> C[Scatter: buckets indexed by frequency]
    C --> D[Gather: sweep from highest bucket]
    D --> E{Collected k items?}
    E -- no --> D
    E -- yes --> F[Answer]

Tiny trace for "tree": counts t=1, r=1, e=2; buckets [1] = {t, r}, [2] = {e}; sweep 2 then 1 -> "eetr".

Java template

import java.util.*;

class BucketCounting {
    // Template 1: stable counting sort for keys in [0, k).
    static int[] countingSort(int[] a, int k) {
        int[] count = new int[k + 1];
        for (int x : a) count[x + 1]++;                    // shift by one for prefix sums
        for (int i = 0; i < k; i++) count[i + 1] += count[i]; // count[v] = start index of v
        int[] out = new int[a.length];
        for (int x : a) out[count[x]++] = x;               // stable placement
        return out;
    }

    // Template 2: bucket by frequency, read highest buckets first.
    static List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int x : nums) freq.merge(x, 1, Integer::sum);

        List<List<Integer>> buckets = new ArrayList<>();
        for (int i = 0; i <= nums.length; i++) buckets.add(new ArrayList<>());
        for (Map.Entry<Integer, Integer> e : freq.entrySet())
            buckets.get(e.getValue()).add(e.getKey());

        List<Integer> res = new ArrayList<>();
        for (int f = nums.length; f >= 1 && res.size() < k; f--) {
            for (int v : buckets.get(f)) {          // sort this bucket first if ties need an order
                if (res.size() == k) break;
                res.add(v);
            }
        }
        return res;
    }

    // Template 3: pigeonhole buckets that only track min and max (Maximum Gap).
    static int maximumGap(int[] a) {
        int n = a.length;
        if (n < 2) return 0;
        int lo = Integer.MAX_VALUE, hi = Integer.MIN_VALUE;
        for (int x : a) { lo = Math.min(lo, x); hi = Math.max(hi, x); }
        if (lo == hi) return 0;
        int width = Math.max(1, (hi - lo) / (n - 1));
        int cnt = (hi - lo) / width + 1;
        int[] bMin = new int[cnt], bMax = new int[cnt];
        Arrays.fill(bMin, Integer.MAX_VALUE);
        Arrays.fill(bMax, Integer.MIN_VALUE);
        for (int x : a) {
            int b = (x - lo) / width;
            bMin[b] = Math.min(bMin[b], x);
            bMax[b] = Math.max(bMax[b], x);
        }
        int best = 0, prevMax = lo;
        for (int b = 0; b < cnt; b++) {
            if (bMin[b] == Integer.MAX_VALUE) continue;   // empty bucket
            best = Math.max(best, bMin[b] - prevMax);
            prevMax = bMax[b];
        }
        return best;
    }
}

Complexity

Variations

• Pure counting array - fixed alphabet or tiny range: Valid Anagram, Sort Colors.
• Frequency buckets - index by count, sweep downward: Sort Characters By Frequency, Top K Frequent Elements.
• Frequency buckets with tie-break - sort words alphabetically inside each bucket: Top K Frequent Words.
• Capped buckets - clamp values above n into bucket n: H-Index.
• Range buckets / pigeonhole - only min and max per bucket matter: Maximum Gap, Contains Duplicate III.
• Radix sort - repeated stable counting sort on each digit for large integer keys.

Common mistakes

• Forgetting to offset negative keys (count[x - min]) before using them as indices.
• Allocating a counting array of size max value when values reach 10^9 - check the range before choosing this pattern.
• Ignoring tie-break rules: Top K Frequent Words wants lexicographic order inside a frequency, so each bucket must be sorted.
• In Maximum Gap, letting the bucket width become 0 when max - min < n - 1; clamp it to at least 1.
• Iterating buckets in the wrong direction (ascending when the question wants most frequent first).

All practice problems

3 problems on this site use this pattern, easiest first. Solve them in order and say the instinct out loud before you code.