# Kth Smallest Pair Distance

# Kth Smallest Pair Distance

Kth Smallest Pair Distance finds the k-th smallest value among all absolute pair differences.

For an array $A$, each pair $(i, j)$ with $i < j$ has distance:

$$
|A[i] - A[j]|
$$

Instead of generating all $O(n^2)$ distances, sort the array and binary search over possible distance values.

## Problem

Given an array $A$ of length $n$ and a 1-based rank $k$, find the k-th smallest pair distance.

There are:

$$
\frac{n(n - 1)}{2}
$$

pairs.

## Algorithm

Sort the array. Then binary search the answer distance $d$. For each candidate $d$, count how many pairs have distance at most $d$.

```id="kspd1"
kth_smallest_pair_distance(A, k):
    sort A

    low = 0
    high = A[n - 1] - A[0]

    while low < high:
        mid = floor((low + high) / 2)

        if count_pairs_at_most(A, mid) < k:
            low = mid + 1
        else:
            high = mid

    return low
```

The counting step uses two pointers.

```id="kspd2"
count_pairs_at_most(A, d):
    count = 0
    left = 0

    for right from 0 to n - 1:
        while A[right] - A[left] > d:
            left = left + 1

        count = count + (right - left)

    return count
```

## Example

Let:

$$
A = [1, 6, 1]
$$

After sorting:

$$
[1, 1, 6]
$$

Pair distances are:

$$
0, 5, 5
$$

For $k = 1$, the answer is:

$$
0
$$

## Correctness

After sorting, the absolute distance for a pair $(i, j)$ with $i < j$ is $A[j] - A[i]$.

For a fixed right endpoint, the two pointer loop finds the smallest left index such that all indices from `left` to `right - 1` form pairs with distance at most $d$. Therefore it adds exactly the number of valid pairs ending at `right`.

The predicate "number of pairs with distance at most $d$ is at least $k$" is monotone. If it holds for a distance $d$, it also holds for every larger distance. Binary search returns the smallest distance for which the predicate holds, which is exactly the k-th smallest pair distance.

## Complexity

| step                              |                             cost |
| --------------------------------- | -------------------------------: |
| sorting                           |                    $O(n \log n)$ |
| one count pass                    |                           $O(n)$ |
| binary search over distance range |                      $O(\log R)$ |
| total                             |         $O(n \log n + n \log R)$ |
| space                             | $O(1)$ extra, aside from sorting |

Here:

$$
R = \max(A) - \min(A)
$$

## When to Use

Use this algorithm when all pair distances are too many to materialize, but the values are numeric and sortable.

It is especially useful when $n$ is large enough that $O(n^2)$ distance generation is infeasible.

## Implementation

```id="kspd3"
def count_pairs_at_most(a, d):
    count = 0
    left = 0

    for right in range(len(a)):
        while a[right] - a[left] > d:
            left += 1

        count += right - left

    return count

def kth_smallest_pair_distance(a, k):
    a.sort()

    low = 0
    high = a[-1] - a[0]

    while low < high:
        mid = (low + high) // 2

        if count_pairs_at_most(a, mid) < k:
            low = mid + 1
        else:
            high = mid

    return low
```

```id="kspd4"
func countPairsAtMost(a []int, d int) int {
	count := 0
	left := 0

	for right := 0; right < len(a); right++ {
		for a[right]-a[left] > d {
			left++
		}

		count += right - left
	}

	return count
}

func KthSmallestPairDistance(a []int, k int) int {
	sortInts(a)

	low := 0
	high := a[len(a)-1] - a[0]

	for low < high {
		mid := low + (high-low)/2

		if countPairsAtMost(a, mid) < k {
			low = mid + 1
		} else {
			high = mid
		}
	}

	return low
}
```