1. The number the code looks for

Imagine the $n$ values of nums in sorted order: $s_0 \le s_1 \le \cdots \le s_{n-1}$. The code never sorts them. The maximum gap is the largest difference between two neighbours, $G = \max_i (s_{i+1} - s_i)$. The code must find $G$ in $O(n)$ time, so it may not sort.

Let lo $= s_0$ and hi $= s_{n-1}$ be the smallest and the largest value.

2. The lower bound on $G$

The $n - 1$ neighbour differences add up to the whole range:

$(s_1 - s_0) + (s_2 - s_1) + \cdots + (s_{n-1} - s_{n-2}) = \text{hi} - \text{lo}$

The largest of $n - 1$ numbers is at least their average. So

$G \ge \frac{\text{hi} - \text{lo}}{n - 1}$

This is the pigeonhole principle at work: $n - 1$ gaps must cover the range, so at least one of them is at least the average size.

3. Buckets, and why the maximum gap is never inside one

The code splits the range into buckets of equal width:

$\text{width} = \max\!\left(1,\ \left\lfloor \frac{\text{hi} - \text{lo}}{n - 1} \right\rfloor\right)$

Bucket $b$ holds the whole numbers from $\text{lo} + b \cdot \text{width}$ to $\text{lo} + (b + 1) \cdot \text{width} - 1$. A value $x$ falls into bucket $\lfloor (x - \text{lo}) / \text{width} \rfloor$.

Two values in the same bucket differ by at most $\text{width} - 1$. By part 2, $G \ge \text{width}$ whenever the values are not all equal. So two values inside one bucket are always closer than $G$, and the maximum gap never lies inside a bucket. It always runs from the largest value of one non-empty bucket to the smallest value of the next non-empty bucket.

So each bucket needs only two numbers, its smallest and its largest value. The code never sorts inside a bucket.

4. The max(1, ...) and the + 1

When $\text{hi} - \text{lo} < n - 1$, the division gives 0, and a width of 0 would divide by zero. max(1, ...) makes the width at least 1. A bucket of width 1 holds one whole number, so values inside it differ by 0, and part 3 still holds.

The number of buckets is (hi - lo) // width + 1. The + 1 makes sure that hi has a bucket: hi falls into bucket $\lfloor (\text{hi} - \text{lo}) / \text{width} \rfloor$, which is the last one.

prev_max starts at lo. The first non-empty bucket is bucket 0, which holds lo, so its first gap is $\text{lo} - \text{lo} = 0$. Empty buckets are skipped, so a gap can run across several of them.

With fewer than two values there is no neighbour at all, so the code returns 0 at once.

5. Example 1 by hand

nums = [3,6,9,1], so $n = 4$, lo = 1 and hi = 9. By part 2, $G \ge \frac{9 - 1}{3} = \frac{8}{3} \approx 2.67$. The code computes width $= \max(1, \lfloor 8 / 3 \rfloor) = 2$ and count $= \lfloor 8 / 2 \rfloor + 1 = 5$ buckets.

The picture shows the five buckets of Example 1, one cell per bucket, with the bucket number under each cell. Each cell holds the value that fell into that bucket, and "-" marks the empty bucket 3. The gap from 6 in bucket 2 to 9 in bucket 4 runs across the empty bucket.

The second loop walks the non-empty buckets and measures each gap from the last bucket's largest value:

The code returns 3, the expected output. The sorted values are 1, 3, 6, 9, and both $6 - 3$ and $9 - 6$ reach 3.

6. Example 2 by hand

nums = [10], so $n = 1$. The check n < 2 is true, and the code returns 0, the expected output.

7. From the math to the code

Because width is the rounded-down average gap, there are never more than $2n - 1$ buckets. So both loops take $O(n)$ time, and the bucket lists take $O(n)$ space.