Maximum Gap (LeetCode 164)
You will see how buckets sized by the pigeonhole principle find the largest gap between sorted neighbours without sorting.
You get an integer array nums. Picture its values sorted from smallest to largest: each pair of values that end up side by side has a difference, and you must return the largest of those differences. If nums holds fewer than two values, there is no such pair, so return 0.
Sorting only defines the answer; it is not a way you may use to find it. Your algorithm has to run in time linear in the length of nums, and it may use extra space that is also linear in it.
Worked Examples
nums = [3,6,9,1]3nums = [10]0⚖️Formal Constraints & Bounds
1 <= nums.length <= 1050 <= nums[i] <= 109
Why It Works & Core Invariant
With width = max(1, (hi - lo) // (n - 1)), no bucket is wider than the smallest possible maximum gap, so the answer never lies inside a bucket: one min and one max per bucket, compared across buckets, is all you need.
Real-World Scenario & Production Applications
Finding the biggest hole in a set of readings: the longest silence between event timestamps, the widest unused block in a range of IDs or ports, the largest jump between sensor values. Bucketing by value finds it in two passes, without sorting millions of readings first.
Step-by-Step Execution Trace Table
Example 1, nums = [3,6,9,1]: n = 4, lo = 1, hi = 9, width = max(1, 8 // 3) = 2, count = 8 // 2 + 1 = 5. After the fill loop, the scan reads:
b | Range | bucket_min[b], bucket_max[b] | Gap bucket_min[b] - prev_max | best | prev_max after |
|---|---|---|---|---|---|
| 0 | 1..2 | 1, 1 | 1 - 1 = 0 | 0 | 1 |
| 1 | 3..4 | 3, 3 | 3 - 1 = 2 | 2 | 3 |
| 2 | 5..6 | 6, 6 | 6 - 3 = 3 | 3 | 6 |
| 3 | 7..8 | empty | skipped by continue: the gap runs across it | 3 | 6 |
| 4 | 9..10 | 9, 9 | 9 - 6 = 3 | 3 | 9 |
| 1 | Don't sort: split `lo..hi` into buckets of equal `width` and drop each value into `b = (x - lo) // width`; the buckets come out in order with no comparisons. |
| 2 | `n` values leave `n - 1` gaps that add up to `hi - lo`, so the largest gap is at least `width`: it never sits inside one bucket. Keep only `bucket_min[b]` and `bucket_max[b]`. |
| 3 | Return `0` if `n < 2`; set `width` and `count = (hi - lo) // width + 1`; fill both lists in one pass; then scan `b` in order, skip empty buckets, and track `best = max(best, bucket_min[b] - prev_max)` with `prev_max = bucket_max[b]`. |
| 4 | The trap: `width = max(1, (hi - lo) // (n - 1))`. With repeated values `hi - lo < n - 1`, the plain quotient is `0`, and `(x - lo) // width` divides by zero. |
Target: Maximum Gap (LeetCode 164). It must come first: with one value, n - 1 is 0 and the width would divide by zero.
Intervals sorted by start coordinate; monotonic stack preserves strictly increasing or decreasing element values.
Sweep: if curr.start <= prev.end: merge; Stack: while stack and nums[i] >= stack[-1]: stack.pop().
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Sorting would answer this at once: sort, then read the differences between neighbours. But the problem asks for linear time, and a comparison sort costs . Bucket Sort avoids comparisons. Split the range from lo = min(nums) to hi = max(nums) into buckets of equal width, and drop each value into its bucket with b = (x - lo) // width: the buckets come out in order without any two values being compared. The values inside one bucket stay unsorted, and that is fine, because with the right width the answer never lives inside a bucket. So each bucket keeps only two numbers, bucket_min[b] and bucket_max[b].
🗄️ The Analogy: Letters in Pigeonholes
A mail room has n letters with house numbers from lo to hi, and a row of pigeonholes, each covering the same stretch of house numbers. You want the biggest jump between two house numbers that come one after the other. The n - 1 jumps together add up to hi - lo, so at least one of them is as long as their average. Make each pigeonhole no longer than that average, and two letters in the same pigeonhole are always closer than the biggest jump. So you never look inside a pigeonhole: you only need its lowest and highest letter, and the biggest jump is always from the highest letter of one pigeonhole to the lowest letter of the next pigeonhole that holds any.
🪄 The Mathematical Harmony / Magic Trick
width = max(1, (hi - lo) // (n - 1))b = (x - lo) // widthbest = max(best, bucket_min[b] - prev_max) This is the pigeonhole principle in three lines. n values leave n - 1 gaps that add up to hi - lo, so the largest gap is at least (hi - lo) / (n - 1); it is a whole number, so when hi > lo it is at least width. Two values that share a bucket differ by at most width - 1, so they can never be the answer: the maximum gap always runs from one bucket's bucket_max to the bucket_min of the next non-empty bucket, called prev_max and bucket_min[b] in the scan. The max(1, ...) matters: when there are more values than steps between lo and hi (hi - lo < n - 1, for example with repeated values), the plain quotient is 0 and (x - lo) // width would divide by zero.
💡 Summary
Bucket by value with width = max(1, (hi - lo) // (n - 1)), keep one min and one max per bucket, then walk the buckets once and measure bucket_min[b] - prev_max across any empty buckets. Two linear passes: time, space.
Zero-width buckets: write
width = max(1, (hi - lo) // (n - 1)). On[1,1,1,4,2],hi - lo = 3is less thann - 1 = 4, so the plain quotient is0and(x - lo) // widthraises a division by zero.Buckets wider than the smallest possible gap: round the width down. With
(hi - lo) // (n - 1) + 1,[6,18]getswidth = 13, both values land in bucket 0, and the answer comes out0instead of12.Comparing neighbouring bucket indices: skip empty buckets and carry
prev_maxfrom the last non-empty one. The largest gap usually runs across empty buckets, sobucket_min[b] - bucket_max[b - 1]misses it or meetsinf.Forgetting the one-value case:
if n < 2: return 0must come first; with one value,n - 1is0and the width itself divides by zero.Sorting anyway:
sorted(nums)gives the right answer inO(N log N), but the problem asks for linear time; the pigeonhole bound onwidthis what makes itO(N).
4-Phase Thought Process Model
You will see how a senior engineer spots a bounded-value gap question and defends pigeonhole buckets out loud.
Pattern Recognition Signals
The 10-second spot
"The maximum difference between successive elements in sorted form" plus "linear time and linear extra space": the answer is defined by sorting, but a comparison sort is too slow. Values bounded by min(nums) and max(nums) and a question about the gaps between them is the signal for Bucket Sort with pigeonhole-sized buckets.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Bucket b holds exactly the values in [lo + b * width, lo + (b + 1) * width), and width = max(1, (hi - lo) // (n - 1)) is at most the smallest possible maximum gap, so the maximum gap is never inside one bucket. Keep bucket_min[b] and bucket_max[b]; for each non-empty bucket, best = max(best, bucket_min[b] - prev_max), then prev_max = bucket_max[b].
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
width = max(1, (hi - lo) // (n - 1)): whenhi - lo < n - 1, as with the repeated values of[1,1,1,4,2], the plain quotient is0and(x - lo) // widthdivides by zero.Round the width down: with
(hi - lo) // (n - 1) + 1,[6,18]getswidth = 13, both values share bucket 0, and the answer comes out0instead of12.Skip empty buckets and keep
prev_maxfrom the last non-empty one: the largest gap usually runs across empty buckets, so comparingbucket_min[b]withbucket_max[b - 1]misses it or meetsinf.if n < 2: return 0comes before the width: with one value,n - 1is0and the width itself divides by zero.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd solve this with Bucket Sort. Sorting defines the answer, but a comparison sort is too slow, so I bucket by value. With n values between lo and hi, the n minus 1 gaps add up to hi minus lo, so the largest gap is at least their average. I make every bucket no wider than that: width is hi minus lo, integer-divided by n minus 1, and at least 1. Two values in the same bucket are closer than the width, so the maximum gap never sits inside a bucket; it always runs from one bucket's maximum to the next non-empty bucket's minimum, so each bucket keeps only its min and max. Then I walk the buckets in order, skip empty ones, and track the largest bucket min minus the previous max. The trap is the floor of 1: with many repeated values the quotient is zero and I'd divide by zero. Two linear passes, so
O(N)time andO(N)space.
So: size the buckets with width = max(1, (hi - lo) // (n - 1)), keep one min and one max each, and compare across buckets only.
Complexity & Mathematical Proof
O(N)
Look at the code: len, min and max each read nums once, O(N). The fill loop for x in nums does one division and two comparisons per value, O(N). The number of buckets is count = (hi - lo) // width + 1. If the quotient (hi - lo) // (n - 1) is at least 1, it is at least half of (hi - lo) / (n - 1), so count <= 2(n - 1) + 1; if it is 0, then width = 1 and hi - lo < n - 1, so count <= n - 1. Either way count is O(N), so building the two bucket lists and the scan for b in range(count) are O(N) too. Total: O(N).
O(N)
bucket_min and bucket_max hold count entries each, so the extra space is O(N); everything else is a handful of numbers, and the answer is one integer.
T(N) = O(N) + O(count) + N · O(1) + count · O(1) = O(N), since count <= 2(N - 1) + 1
Look at the code: len, min and max each read nums once, O(N). The fill loop for x in nums does one division and two comparisons per value, O(N). The number of buckets is count = (hi - lo) // width + 1. If the quotient (hi - lo) // (n - 1) is at least 1, it is at least half of (hi - lo) / (n - 1), so count <= 2(n - 1) + 1; if it is 0, then width = 1 and hi - lo < n - 1, so count <= n - 1. Either way count is O(N), so building the two bucket lists and the scan for b in range(count) are O(N) too. Total: O(N).
Derivation Progression
O(N)
len(nums), min(nums) and max(nums) each read nums once.
O(count) = O(N)
[float("inf")] * count and [float("-inf")] * count; count <= 2(N - 1) + 1.
N · O(1)
for x in nums: one division (x - lo) // width, one min and one max per value.
count · O(1)
for b in range(count): one emptiness check, then at most one subtraction, one max and one assignment per bucket.
O(N)
Two linear passes over the values and one over at most 2(N - 1) + 1 buckets.
Variable Definitions
Number of values, len(nums) (called n in the code)
Bucket width, max(1, (hi - lo) // (n - 1))
Number of buckets, (hi - lo) // width + 1, at most 2(N - 1) + 1
Memory Architecture & Bounds
O(1) Iterative, no recursion
O(N): bucket_min and bucket_max, count entries each
O(1): one integer
Boundary Best / Worst Cases
: one value, so if n < 2: return 0 answers at once
: every value is bucketed and every bucket is scanned
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "the maximum difference between successive elements in sorted form", "linear time and linear extra space". The answer is defined by sorting, but a comparison sort is too slow: Bucket Sort with pigeonhole-sized buckets, keeping one min and one max per bucket.
values up to . Sorting costs comparisons, and a counting array indexed by value would need slots. Pigeonhole buckets need at most slots and two linear passes: time and space.
width = max(1, (hi - lo) // (n - 1)): without the floor of 1, heavy duplicates make the width 0. On a stream, lo and hi must be known before the first value is bucketed, so the data needs one pass for the bounds and one for the buckets. On sharded data, each shard can report its own bucket_min and bucket_max for the same lo and width, and merging them is one min and one max per bucket. x - lo stays below , so it fits a 32-bit integer.
Core Algorithmic State Invariants
`n` values from `lo` to `hi` leave `n - 1` gaps that add up to `hi - lo`, so the largest gap is at least `width = max(1, (hi - lo) // (n - 1))`. Two values in one bucket differ by at most `width - 1`, so the answer is never inside a bucket.
`b = (x - lo) // width` drops each value into its bucket with no comparison between values. Only `bucket_min[b]` and `bucket_max[b]` matter, because the gap always runs from a bucket's max to a later bucket's min.
Walk `b` from `0` to `count - 1`, skip empty buckets, and measure `bucket_min[b] - prev_max`, where `prev_max` is the last non-empty bucket's max. `count <= 2(n - 1) + 1`, so both passes are O(N).
Maximum Gap (LeetCode 164)
You will see how buckets sized by the pigeonhole principle find the largest gap between sorted neighbours without sorting.
You get an integer array nums. Picture its values sorted from smallest to largest: each pair of values that end up side by side has a difference, and you must return the largest of those differences. If nums holds fewer than two values, there is no such pair, so return 0.
Sorting only defines the answer; it is not a way you may use to find it. Your algorithm has to run in time linear in the length of nums, and it may use extra space that is also linear in it.
Worked Examples
nums = [3,6,9,1]3nums = [10]0⚖️Formal Constraints & Bounds
1 <= nums.length <= 1050 <= nums[i] <= 109
Why It Works & Core Invariant
With width = max(1, (hi - lo) // (n - 1)), no bucket is wider than the smallest possible maximum gap, so the answer never lies inside a bucket: one min and one max per bucket, compared across buckets, is all you need.
Real-World Scenario & Production Applications
Finding the biggest hole in a set of readings: the longest silence between event timestamps, the widest unused block in a range of IDs or ports, the largest jump between sensor values. Bucketing by value finds it in two passes, without sorting millions of readings first.
Step-by-Step Execution Trace Table
Example 1, nums = [3,6,9,1]: n = 4, lo = 1, hi = 9, width = max(1, 8 // 3) = 2, count = 8 // 2 + 1 = 5. After the fill loop, the scan reads:
b | Range | bucket_min[b], bucket_max[b] | Gap bucket_min[b] - prev_max | best | prev_max after |
|---|---|---|---|---|---|
| 0 | 1..2 | 1, 1 | 1 - 1 = 0 | 0 | 1 |
| 1 | 3..4 | 3, 3 | 3 - 1 = 2 | 2 | 3 |
| 2 | 5..6 | 6, 6 | 6 - 3 = 3 | 3 | 6 |
| 3 | 7..8 | empty | skipped by continue: the gap runs across it | 3 | 6 |
| 4 | 9..10 | 9, 9 | 9 - 6 = 3 | 3 | 9 |
| 1 | Don't sort: split `lo..hi` into buckets of equal `width` and drop each value into `b = (x - lo) // width`; the buckets come out in order with no comparisons. |
| 2 | `n` values leave `n - 1` gaps that add up to `hi - lo`, so the largest gap is at least `width`: it never sits inside one bucket. Keep only `bucket_min[b]` and `bucket_max[b]`. |
| 3 | Return `0` if `n < 2`; set `width` and `count = (hi - lo) // width + 1`; fill both lists in one pass; then scan `b` in order, skip empty buckets, and track `best = max(best, bucket_min[b] - prev_max)` with `prev_max = bucket_max[b]`. |
| 4 | The trap: `width = max(1, (hi - lo) // (n - 1))`. With repeated values `hi - lo < n - 1`, the plain quotient is `0`, and `(x - lo) // width` divides by zero. |
Target: Maximum Gap (LeetCode 164). It must come first: with one value, n - 1 is 0 and the width would divide by zero.
Intervals sorted by start coordinate; monotonic stack preserves strictly increasing or decreasing element values.
Sweep: if curr.start <= prev.end: merge; Stack: while stack and nums[i] >= stack[-1]: stack.pop().
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Sorting would answer this at once: sort, then read the differences between neighbours. But the problem asks for linear time, and a comparison sort costs . Bucket Sort avoids comparisons. Split the range from lo = min(nums) to hi = max(nums) into buckets of equal width, and drop each value into its bucket with b = (x - lo) // width: the buckets come out in order without any two values being compared. The values inside one bucket stay unsorted, and that is fine, because with the right width the answer never lives inside a bucket. So each bucket keeps only two numbers, bucket_min[b] and bucket_max[b].
🗄️ The Analogy: Letters in Pigeonholes
A mail room has n letters with house numbers from lo to hi, and a row of pigeonholes, each covering the same stretch of house numbers. You want the biggest jump between two house numbers that come one after the other. The n - 1 jumps together add up to hi - lo, so at least one of them is as long as their average. Make each pigeonhole no longer than that average, and two letters in the same pigeonhole are always closer than the biggest jump. So you never look inside a pigeonhole: you only need its lowest and highest letter, and the biggest jump is always from the highest letter of one pigeonhole to the lowest letter of the next pigeonhole that holds any.
🪄 The Mathematical Harmony / Magic Trick
width = max(1, (hi - lo) // (n - 1))b = (x - lo) // widthbest = max(best, bucket_min[b] - prev_max) This is the pigeonhole principle in three lines. n values leave n - 1 gaps that add up to hi - lo, so the largest gap is at least (hi - lo) / (n - 1); it is a whole number, so when hi > lo it is at least width. Two values that share a bucket differ by at most width - 1, so they can never be the answer: the maximum gap always runs from one bucket's bucket_max to the bucket_min of the next non-empty bucket, called prev_max and bucket_min[b] in the scan. The max(1, ...) matters: when there are more values than steps between lo and hi (hi - lo < n - 1, for example with repeated values), the plain quotient is 0 and (x - lo) // width would divide by zero.
💡 Summary
Bucket by value with width = max(1, (hi - lo) // (n - 1)), keep one min and one max per bucket, then walk the buckets once and measure bucket_min[b] - prev_max across any empty buckets. Two linear passes: time, space.
Zero-width buckets: write
width = max(1, (hi - lo) // (n - 1)). On[1,1,1,4,2],hi - lo = 3is less thann - 1 = 4, so the plain quotient is0and(x - lo) // widthraises a division by zero.Buckets wider than the smallest possible gap: round the width down. With
(hi - lo) // (n - 1) + 1,[6,18]getswidth = 13, both values land in bucket 0, and the answer comes out0instead of12.Comparing neighbouring bucket indices: skip empty buckets and carry
prev_maxfrom the last non-empty one. The largest gap usually runs across empty buckets, sobucket_min[b] - bucket_max[b - 1]misses it or meetsinf.Forgetting the one-value case:
if n < 2: return 0must come first; with one value,n - 1is0and the width itself divides by zero.Sorting anyway:
sorted(nums)gives the right answer inO(N log N), but the problem asks for linear time; the pigeonhole bound onwidthis what makes itO(N).
4-Phase Thought Process Model
You will see how a senior engineer spots a bounded-value gap question and defends pigeonhole buckets out loud.
Pattern Recognition Signals
The 10-second spot
"The maximum difference between successive elements in sorted form" plus "linear time and linear extra space": the answer is defined by sorting, but a comparison sort is too slow. Values bounded by min(nums) and max(nums) and a question about the gaps between them is the signal for Bucket Sort with pigeonhole-sized buckets.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Bucket b holds exactly the values in [lo + b * width, lo + (b + 1) * width), and width = max(1, (hi - lo) // (n - 1)) is at most the smallest possible maximum gap, so the maximum gap is never inside one bucket. Keep bucket_min[b] and bucket_max[b]; for each non-empty bucket, best = max(best, bucket_min[b] - prev_max), then prev_max = bucket_max[b].
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
width = max(1, (hi - lo) // (n - 1)): whenhi - lo < n - 1, as with the repeated values of[1,1,1,4,2], the plain quotient is0and(x - lo) // widthdivides by zero.Round the width down: with
(hi - lo) // (n - 1) + 1,[6,18]getswidth = 13, both values share bucket 0, and the answer comes out0instead of12.Skip empty buckets and keep
prev_maxfrom the last non-empty one: the largest gap usually runs across empty buckets, so comparingbucket_min[b]withbucket_max[b - 1]misses it or meetsinf.if n < 2: return 0comes before the width: with one value,n - 1is0and the width itself divides by zero.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd solve this with Bucket Sort. Sorting defines the answer, but a comparison sort is too slow, so I bucket by value. With n values between lo and hi, the n minus 1 gaps add up to hi minus lo, so the largest gap is at least their average. I make every bucket no wider than that: width is hi minus lo, integer-divided by n minus 1, and at least 1. Two values in the same bucket are closer than the width, so the maximum gap never sits inside a bucket; it always runs from one bucket's maximum to the next non-empty bucket's minimum, so each bucket keeps only its min and max. Then I walk the buckets in order, skip empty ones, and track the largest bucket min minus the previous max. The trap is the floor of 1: with many repeated values the quotient is zero and I'd divide by zero. Two linear passes, so
O(N)time andO(N)space.
So: size the buckets with width = max(1, (hi - lo) // (n - 1)), keep one min and one max each, and compare across buckets only.
Complexity & Mathematical Proof
O(N)
Look at the code: len, min and max each read nums once, O(N). The fill loop for x in nums does one division and two comparisons per value, O(N). The number of buckets is count = (hi - lo) // width + 1. If the quotient (hi - lo) // (n - 1) is at least 1, it is at least half of (hi - lo) / (n - 1), so count <= 2(n - 1) + 1; if it is 0, then width = 1 and hi - lo < n - 1, so count <= n - 1. Either way count is O(N), so building the two bucket lists and the scan for b in range(count) are O(N) too. Total: O(N).
O(N)
bucket_min and bucket_max hold count entries each, so the extra space is O(N); everything else is a handful of numbers, and the answer is one integer.
T(N) = O(N) + O(count) + N · O(1) + count · O(1) = O(N), since count <= 2(N - 1) + 1
Look at the code: len, min and max each read nums once, O(N). The fill loop for x in nums does one division and two comparisons per value, O(N). The number of buckets is count = (hi - lo) // width + 1. If the quotient (hi - lo) // (n - 1) is at least 1, it is at least half of (hi - lo) / (n - 1), so count <= 2(n - 1) + 1; if it is 0, then width = 1 and hi - lo < n - 1, so count <= n - 1. Either way count is O(N), so building the two bucket lists and the scan for b in range(count) are O(N) too. Total: O(N).
Derivation Progression
O(N)
len(nums), min(nums) and max(nums) each read nums once.
O(count) = O(N)
[float("inf")] * count and [float("-inf")] * count; count <= 2(N - 1) + 1.
N · O(1)
for x in nums: one division (x - lo) // width, one min and one max per value.
count · O(1)
for b in range(count): one emptiness check, then at most one subtraction, one max and one assignment per bucket.
O(N)
Two linear passes over the values and one over at most 2(N - 1) + 1 buckets.
Variable Definitions
Number of values, len(nums) (called n in the code)
Bucket width, max(1, (hi - lo) // (n - 1))
Number of buckets, (hi - lo) // width + 1, at most 2(N - 1) + 1
Memory Architecture & Bounds
O(1) Iterative, no recursion
O(N): bucket_min and bucket_max, count entries each
O(1): one integer
Boundary Best / Worst Cases
: one value, so if n < 2: return 0 answers at once
: every value is bucketed and every bucket is scanned
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "the maximum difference between successive elements in sorted form", "linear time and linear extra space". The answer is defined by sorting, but a comparison sort is too slow: Bucket Sort with pigeonhole-sized buckets, keeping one min and one max per bucket.
values up to . Sorting costs comparisons, and a counting array indexed by value would need slots. Pigeonhole buckets need at most slots and two linear passes: time and space.
width = max(1, (hi - lo) // (n - 1)): without the floor of 1, heavy duplicates make the width 0. On a stream, lo and hi must be known before the first value is bucketed, so the data needs one pass for the bounds and one for the buckets. On sharded data, each shard can report its own bucket_min and bucket_max for the same lo and width, and merging them is one min and one max per bucket. x - lo stays below , so it fits a 32-bit integer.
Core Algorithmic State Invariants
`n` values from `lo` to `hi` leave `n - 1` gaps that add up to `hi - lo`, so the largest gap is at least `width = max(1, (hi - lo) // (n - 1))`. Two values in one bucket differ by at most `width - 1`, so the answer is never inside a bucket.
`b = (x - lo) // width` drops each value into its bucket with no comparison between values. Only `bucket_min[b]` and `bucket_max[b]` matter, because the gap always runs from a bucket's max to a later bucket's min.
Walk `b` from `0` to `count - 1`, skip empty buckets, and measure `bucket_min[b] - prev_max`, where `prev_max` is the last non-empty bucket's max. `count <= 2(n - 1) + 1`, so both passes are O(N).
| Canonical Invariant | Concrete Code | Engineering Rationale |
|---|---|---|
| No neighbours, no gap | if n < 2:
return 0 | It must come first: with one value, n - 1 is 0 and the width would divide by zero. |
| Bounds of the value range | lo, hi = min(nums), max(nums) | Every bucket is placed relative to lo, and the buckets must reach hi. |
| Bucket width from the pigeonhole bound, never 0 | width = max(1, (hi - lo) // (n - 1)) | The largest gap is at least (hi - lo) / (n - 1), so a bucket this wide can never hold it; max(1, ...) stops repeated values from making the width 0. |
| Enough buckets to hold hi | count = (hi - lo) // width + 1 | hi falls into bucket (hi - lo) // width, so that index needs a slot too. |
| Drop each value into its bucket and keep only the extremes | b = (x - lo) // width
bucket_min[b] = min(bucket_min[b], x)
bucket_max[b] = max(bucket_max[b], x) | No two values are compared; a bucket's inside never holds the answer, so its min and max are all that matter. |
| Compare across buckets only, skipping empty ones | if bucket_min[b] == float("inf"):
continue
best = max(best, bucket_min[b] - prev_max)
prev_max = bucket_max[b] | The next value up after a bucket's max is the next non-empty bucket's min, so each gap is one subtraction. |
| Answer | return best | The largest gap between sorted neighbours, found without sorting. |