Bucketing by value range

55 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

Six numbers: 3, 6, 9, 1, 14, 20. What is the largest gap between two of them when they are sorted? Sort: 1, 3, 6, 9, 14, 20; the gaps are 2, 3, 3, 5, 6; the largest is 6. Sorting is the obvious route and it costs about n log n comparisons. The problem asks for a linear-time answer, which means we may not sort. That sounds impossible until you notice that most of the sorting was wasted: we never needed the exact order inside small clusters of values, only the distances between clusters.

Build the structure, one piece at a time

Piece one: a width. The numbers range from 1 to 20, a span of 19, and there are 6 of them, so 5 gaps. The gaps cannot all be small: if every gap were below 19/5, the sorted numbers would not reach from 1 to 20. So some gap is at least ⌈19/5⌉ = 4. Call w = 4 the bucket width.

largest gap ≥ (max − min) / (n − 1)

Piece two: buckets of that width. Number v goes to bucket ⌊(v − min) / w⌋. Each bucket remembers only two things, its smallest and largest value; it does not store the values themselves:

Piece three: the answer. Any two values in the same bucket are less than w apart, and we know the answer is at least w, so the largest gap must be between buckets. Walk the buckets left to right and take each bucket's min minus the previous non-empty bucket's max: 6 − 3 = 3, 9 − 6 = 3, 14 − 9 = 5, 20 − 14 = 6. The largest is 6.

The same bucketing answers "is any earlier value within t of this one?" in Contains Duplicate III: use width t + 1, and two values within t must be in the same bucket or in adjacent buckets, so each arrival checks three buckets.

Why it is correct

The invariant is that each bucket's min and max are the true smallest and largest values that fell into it. Two facts make the gap answer right. First, the largest gap is at least w, shown above by the pigeonhole argument. Second, any gap inside one bucket is at most w − 1, because the bucket's value range has width w. So the largest gap lies between two consecutive non-empty buckets, and between those two buckets the largest possible gap is exactly the next bucket's min minus this bucket's max, since those two values are the sorted neighbours across the boundary.

For the "within t" question, if |x − y| ≤ t then their bucket numbers differ by at most 1, because moving by at most t cannot cross two boundaries that are t + 1 apart.

Why it is fast

Finding the min and max is one pass. Placing each value is one division and two comparisons, another pass. Walking the buckets is one pass over at most n buckets. Everything is O(n) time and O(n) memory, against O(n log n) for sorting. The trade is that we learn nothing about the order within a bucket, which this question never needed.

How to recognise it in an interview

Cues: "in linear time", "maximum gap", "any two elements within t", "difference at most k", values that are integers in a known range. Say: "the answer only depends on which values are close, so I will bucket by value with a width chosen so that close values share a bucket or a neighbour".

Maximum Gap is the walk-through above. Contains Duplicate III uses width t + 1 and a dictionary of buckets for the sliding window, checking the same and adjacent buckets on each arrival and deleting the bucket of the value that leaves. K-diff Pairs in an Array needs only a hash map of counts, which is bucketing with width 1.

02The idea in one line

Bucket id = value // (t+1); near values land in the same or neighbouring bucket.

Reach for it when: Contains duplicate III, maximum gap, k-diff pairs.

Cost: O(n) time.

03The walk-through, step by step

The video works one example: Maximum Gap on [3,6,9,1] with buckets. These are its captions in order, so you can follow without the video or check a step you missed.

1. n numbers in range [1,20]: some gap is at least ⌈19/5⌉ = 4, the bucket width
2. 3 → bucket 0: update its min/max
3. 6 → bucket 1: update its min/max
4. 9 → bucket 2: update its min/max
5. 1 → bucket 0: update its min/max
6. 14 → bucket 3: update its min/max
7. 20 → bucket 4: update its min/max
8. Gaps inside a bucket are < width, so only gaps between buckets matter
9. gap = min of bucket 1 − max of bucket 0 = 6 − 3 = 3
10. gap = min of bucket 2 − max of bucket 1 = 9 − 6 = 3
11. gap = min of bucket 3 − max of bucket 2 = 14 − 9 = 5
12. gap = min of bucket 4 − max of bucket 3 = 20 − 14 = 6
13. Maximum gap = 6 (between 9 and 14)
14. Linear buckets instead of sorting: O(n) time and space

04Asked at Google

4 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 Advanced Structures: Segment tree (range query + point update), Fenwick tree (binary indexed tree), Ordered set / sorted container, Matrix exponentiation for recurrences, Meet in the middle.