787. The kth Smallest Distance in a List

Given n integers, form |a[i] - a[j]| for every pair of POSITIONS with i < j. There are n (n - 1) / 2 such distances. Print the kth smallest, counting from 1.

list 1 3 6 10, k = 3 -> 4 distances 2 3 4 5 7 9 list 1 3 6 10, k = 6 -> 9 list 4 4 4 4 4, k = 1 -> 0 every pair is zero apart list -7 -3 0 2 9, k = 4 -> 5 distances 2 3 4 5 7 7 9 9 12 16

Read that last line twice. Ten pairs produce only eight DISTINCT distances: 7 occurs both as -7 against 0 and as 2 against 9, and 9 occurs both as -7 against 2 and as 0 against 9. Position 4 of the multiset, duplicates counted, is 5.

Collapsing those duplicates would not change this particular answer, and that is exactly why the mistake is easy to make and hard to notice. It changes the answer for k = 6, where the multiset gives 7 and the distinct set gives 9.

## Listing the distances is quadratic

At n = 10^5 there are about 5 * 10^9 distances. The kth one is wanted, not the list, so count rather than enumerate.

## Counting distances at most x

Sort the values. Then |a[i] - a[j]| for i < j becomes a[j] - a[i] with i < j in sorted order, and a window does the counting:

lo = 0, count = 0 for hi in 0 .. n-1: while a[hi] - a[lo] > x: lo += 1 count += hi - lo

For each right end, lo is the leftmost partner still within x, so every index from lo to hi - 1 pairs with hi. lo never moves backwards as hi advances, because widening the right end can only push the window's left edge right, so the whole pass is O(n).

## Why the count is monotone

A pair within x is still within x + 1, so the count never falls. Nothing else is needed.

## Why the answer is a distance that really occurs

Search for the smallest x with count(x) >= k. Then count(x - 1) < k, so some pair has a distance in (x - 1, x], and distances between integers are integers, so a pair is exactly x apart. The list 4 4 4 4 4 is worth checking: every distance is 0, so count is 10 from x = 0 onwards and 0 has to be reachable, which it is only because the lower bound starts at 0 and not at 1.

## The bounds

lo = 0, because two equal values are a legal pair and 0 is a legal answer. hi = a[n-1] - a[0] after sorting, the largest distance there is.

Starting the search at lo = 1 is the most common mistake in this problem. It is invisible unless the input contains a repeated value, and then it returns 1 for a list whose smallest distance is 0.

## The boundary that breaks a careless implementation

The inner while must be a while, not an if. One step of lo is enough only when the values are close together; with 1 1 1 1 1000000 and a small x the window has to collapse by FOUR positions at once. At the right end 1000000 the left edge moves from 0 straight to 4, and an if leaves it at 1 and then adds three pairs that are a million apart.

## Overflow

Two values at opposite ends of -10^9 .. 10^9 are 2000000000 apart, which is inside the 2147483647 a signed integer held in 32 bits reaches, so the distances and the bounds are safe there. The count is not:

count up to n (n - 1) / 2 = 4999950000 at n = 100000

k is allowed to reach that, so k and the running count are both 64-bit. The last test in the list forces it: fifty thousand copies of -10^9 followed by fifty thousand copies of 10^9, with k at its maximum. The answer is 2000000000, and a build with every long long replaced by int prints 0.

## Where else this lives in the bank

Problem 269 counts the pairs at a FIXED distance and never ranks them. Problem 783 runs this same search over pair TOTALS, where the counter becomes two pointers closing in from the ends rather than a window sliding rightwards. The search skeleton is identical in all three; only the counter changes, and that is the transferable part.

## Cost

Time O(n log n + n log(range)). Space O(n).

Constraints - `2 ≤ n ≤ 100000` - `1 ≤ k ≤ n * (n - 1) / 2` - `-10^9 ≤ a[i] ≤ 10^9`