Unseen Problem Example: The Smallest Gap Between Two Readings

Up to 50,000 readings rule out comparing every pair, and sorting puts the closest two side by side.

The six steps for an unseen problem, applied here to a list of numbers, show the limits forcing something faster than the obvious answer. A greenhouse logs up to 50,000 temperature readings, whole numbers that may be negative or repeated, and you must report the smallest difference between any two of them. The brute force compares every pair; the faster approach sorts first, which puts the closest two readings side by side. The table records what each step decided.

The six steps on the smallest gap between two readings
Step	What it decided
Clarify	n ≤ 50,000; at least two readings; whole numbers, possibly negative or repeated; the answer is the smallest difference and the pair that gives it
Work examples	31 4 18 9 27 gives 4, between 27 and 31; the edge case 8 3 8 gives 0, from the repeated 8
Brute force	Compare every pair: O(n²). For n = 50,000, n² is 2.5 × 10⁹, far past the budget of about 10⁸ steps a second
Bottleneck	Every pair is compared, but in sorted order the closest pair must be neighbours, so only n − 1 gaps need checking
Write	Sort, then take the smallest gap between neighbours: O(n log n), under 10⁶ steps for n = 50,000
Trace	The run below, on the example and three edge cases

Sorting works because order turns a question about every pair into a question about neighbours. If a, b and c are sorted with b between the other two, the gap from a to c is at least the gap from a to b, so no pair that skips over a reading can be the closest. The Python run prints the sorted readings with the gap between each neighbouring pair beneath them, then three edge cases: two readings, a repeated reading, and negative readings.

smallest_gap.pypy

def smallest_gap(readings: list[int]) -> tuple[int, int, int]:
    ordered = sorted(readings)
    gaps = [ordered[i + 1] - ordered[i] for i in range(len(ordered) - 1)]
    print("sorted:", *ordered)
    print("gaps:  ", *gaps)
    best = min(range(len(gaps)), key=lambda i: gaps[i])
    return gaps[best], ordered[best], ordered[best + 1]


gap, lower, upper = smallest_gap([31, 4, 18, 9, 27])
print(f"smallest gap: {gap}, between {lower} and {upper}")
for readings in ([12, 5], [8, 3, 8], [-7, 2, -4]):
    print(*readings, "->", smallest_gap(readings)[0])

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

sorted: 4 9 18 27 31
gaps:   5 9 9 4
smallest gap: 4, between 27 and 31
sorted: 5 12
gaps:   7
12 5 -> 7
sorted: 3 8 8
gaps:   5 0
8 3 8 -> 0
sorted: -7 -4 2
gaps:   3 6
-7 2 -4 -> 3

The repeated reading gives a gap of 0, the smallest possible, and the negative readings need no special handling, because a later sorted neighbour minus an earlier one is never negative. The answer carries the pair as well as the gap, since the clarify step settled that the pair is part of what to report. The step that mattered was the fourth: naming the bottleneck as every pair compared is what pointed at sorting.

← → move through sections and cards