Bucket / counting sort

44 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

A researcher has five papers with citation counts 3, 0, 6, 1, 5. The h-index is the largest h such that at least h papers have at least h citations each. Try h = 3: the papers with 3 or more citations are 3, 6, 5, that is three papers, so h = 3 works. Try h = 4: only 6 and 5 have four or more, two papers, so it fails. The answer is 3.

By hand you would sort the counts, 6, 5, 3, 1, 0, and walk down until the position number exceeds the count. Sorting costs about n log₂ n comparisons. Can we avoid comparing at all?

Notice that the h-index can never exceed n, the number of papers. A paper with 1000 citations is no more useful than a paper with n citations. So the only values that matter are 0, 1, …, n: a small, known set. When the keys come from a small known range, we can count them instead of sorting them.

Build the structure, one piece at a time

Piece 1: buckets. Make n + 1 empty boxes labelled 0 to n. Here, six boxes labelled 0 to 5.

Piece 2: drop each item in its box. A paper with c citations goes into box min(c, n). Papers 3, 0, 6, 1, 5 go into boxes 3, 0, 5, 1, 5.

Piece 3: read the boxes from the top. Walk h downward from n, keeping a running total of papers in boxes ≥ h. Stop at the first h where the total is at least h.

Reading the boxes in order is also a sort: emptying boxes 0, 1, …, n in turn lists the counts in increasing order. That is counting sort, and it never compared two values.

Why it is correct

The invariant: box v holds exactly the papers whose (capped) citation count is v, and the running total at step h is the number of papers with at least h citations.

The first part is by construction. For the second, the total after adding boxes n, n − 1, …, h is the number of papers with capped count ≥ h, and since h ≤ n, capping at n does not change whether a count is ≥ h. The condition "at least h papers have at least h citations" is therefore tested exactly, and we stop at the largest h that passes because we walk downward.

h-index = max { h : #{papers with citations ≥ h} ≥ h }, with h ≤ n always

Why it is fast

Dropping n papers into boxes is n steps. Reading n + 1 boxes is n + 1 steps.

time = O(n + range), here O(n), versus O(n log n) for sorting

The trade is memory for the boxes. It pays off whenever the range of keys is about the size of the input or smaller: citation counts capped at n, frequencies (at most n), colours (3 of them), characters (26 or 256). It does not pay off when keys can be anything up to a billion, unless you bucket by ranges of values instead of exact values, which is the idea behind the maximum-gap trick.

How to recognise it in an interview

The cues are a small key range stated or implied: "values are between 0 and 100", "frequencies", "letters", "colours 0, 1, 2", "at most n", plus a demand for linear time. Say: "The keys live in a small range, so I count into buckets instead of sorting."

H-Index is the example above. Top K Frequent Elements puts each value into a bucket indexed by its frequency, then reads the buckets from the top until k values are collected, which is O(n). Sort Colors is counting sort with three buckets (or the Dutch flag one-pass version). Maximum Gap buckets a million values into about n ranges and shows the largest gap must be between buckets, not inside one.

02The idea in one line

Bounded keys: count into buckets instead of comparing.

Reach for it when: Top-k by frequency, H-index, maximum gap, sort colours.

Cost: O(n + range) time.

03The walk-through, step by step

The video works one example: H-Index on [3,0,6,1,5]. These are its captions in order, so you can follow without the video or check a step you missed.

1. Citations above n = 5 count as 5: bucket by count instead of sorting
2. paper with 3 citations → bucket 3
3. paper with 0 citations → bucket 0
4. paper with 6 citations → bucket 5
5. paper with 1 citations → bucket 1
6. paper with 5 citations → bucket 5
7. Scan buckets from the top, accumulating papers with ≥ k citations
8. k = 5: 2 papers have ≥ 5 citations, 2 < 5, keep going
9. k = 4: 2 papers have ≥ 4 citations, 2 < 4, keep going
10. k = 3: 3 papers have ≥ 3 citations, 3 ≥ 3 → h = 3
11. Buckets replace the sort: O(n) time

04Asked at Google

7 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Sorting: Custom comparator / key sort, Cyclic sort (1..n placement), Quickselect (kth element), Merge sort with counting.