A bucket is a place that holds every value inside one range. Bucket Sort puts each value into its bucket with one formula, b = (x - lo) // width. The formula uses only x, lo and width. It never compares x with another value.

The buckets are laid out in order. Bucket 0 holds the smallest values and the last bucket holds the largest. So after the placing loop, the values are already ordered between buckets. Only the order inside one bucket is unknown.

The key can be any bounded number. In maximum_gap the key is the value itself, cut into ranges of width numbers. In Top K Frequent Elements (LC 347) and Sort Characters By Frequency (LC 451) the key is a count. A count is never more than the input length, so buckets[count] can hold every item with that count.

For example, take nums = [1, 1, 1, 2, 2, 3] and k = 2. The counts are 3 for the value 1, 2 for the value 2 and 1 for the value 3. buckets[3] holds [1], buckets[2] holds [2] and buckets[1] holds [3]. Reading buckets from the last index down gives 1, then 2, so the answer is [1, 2].

Take nums = [1, 2, 10, 4, 25, 7]. Here n = 6, lo = 1 and hi = 25. So width = max(1, 24 // 5) = 4, and count = 24 // 4 + 1 = 7 buckets.

The placing loop gives these buckets. Bucket 0 holds 1, 2 and 4, so its minimum is 1 and its maximum is 4. Bucket 1 holds 7. Bucket 2 holds 10. Buckets 3, 4 and 5 stay empty. Bucket 6 holds 25.

The walk starts with prev_max = lo = 1. Bucket 0 gives a gap of 1 - 1 = 0. Bucket 1 gives 7 - 4 = 3, and bucket 2 gives 10 - 7 = 3. The board marks buckets 3, 4 and 5 as skipped.

Bucket 6 gives 25 - 10 = 15. The last non-empty bucket before it is bucket 2, not bucket 5. This is the trap on the board: bucket_max[5] is -inf, so the formula with bucket_max[b - 1] would give inf. The variable prev_max is 10 and gives the right gap.

The answer is 15. On the LeetCode example [3, 6, 9, 1] the same code returns 3.

There are n values, so there are n - 1 gaps between sorted neighbours. The gaps add up to hi - lo. The largest gap is at least the average, (hi - lo) / (n - 1). A gap is a whole number, so the largest gap is at least (hi - lo) // (n - 1), which is width, whenever hi > lo. This is the pigeonhole principle.

A bucket covers width whole numbers, so two values in one bucket differ by at most width - 1. That is smaller than width. So no pair inside one bucket can be the largest gap. The largest gap always starts at the maximum of one non-empty bucket and ends at the minimum of a later non-empty bucket. The other values in a bucket never matter, so each bucket keeps only bucket_min and bucket_max.

The first trap is width = (hi - lo) // (n - 1) with no floor of 1. For nums = [1, 1, 1, 4, 2], hi - lo = 3 and n - 1 = 4, so the result is 0 and the next division raises a ZeroDivisionError. With max(1, ...), width = 1 and the answer is 2. The second trap is a width rounded up with + 1. For nums = [6, 18] the width becomes 13, both values share bucket 0, and the code returns 0 instead of 12.

The placing loop does O(n) work and the walk visits every bucket once. The number of buckets is (hi - lo) // width + 1, which is less than 2n. So the time is O(n) and the space is O(n). Sorting first costs O(n log n).

Buckets need the range to be known before the data is placed. If the values arrive one at a time and the answer is needed after each arrival, as in Kth Largest Element in a Stream (LC 703), there is no range to lay out. Use a heap there.

If every value is a small whole number, one slot per exact value is enough and no range is needed. That is the next card, Counting Sort.