Find K-th Smallest Pair Distance — Hard Problem & Solution

The distance of a pair (a, b) is |a - b|. Given nums, return the k-th smallest distance among all n · (n - 1) / 2 index pairs.

Difficulty: Hard
Topics: Arrays, Sorting, Two Pointers, Binary Search
Asked at: Amazon, Google, Apple
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

The distance of a pair (a, b) is |a - b|.

Given nums, return the k-th smallest distance among all n · (n - 1) / 2 index pairs.

Example 1

Input: nums = [1,3,1], k = 1
Output: 0
Explanation: The three distances are 0, 2 and 2.

Example 2

Input: nums = [1,1,1], k = 2
Output: 0

Example 3

Input: nums = [1,6,1], k = 3
Output: 5
Explanation: The distances are 0, 5 and 5.

Constraints

2 <= nums.length <= 10000
0 <= nums[i] <= 1000000
1 <= k <= nums.length · (nums.length - 1) / 2

How to solve Find K-th Smallest Pair Distance

Binary search over the distance rather than over the data. Counting pairs within a given distance is cheap on a sorted array, and the count is monotone in the distance, so the smallest distance whose count reaches k is the answer.

Approach

Sort nums. The candidate distances lie in [0, max - min].
countLE(d): slide r forward, advancing l while s[r] - s[l] > d; each r contributes r - l pairs.
Binary search the smallest d with countLE(d) >= k.

Why it works

countLE is non-decreasing in d, so the predicate countLE(d) >= k flips exactly once — that boundary is the k-th smallest distance, because a distance is achieved by some pair precisely when the count strictly increases there. The sweep is linear: l only moves right, since a larger s[r] can only push the feasible start further along.

Complexity

Time — O(n log n + n log M) where M is the value range
Space — O(n)

Pitfalls

Binary searching on indices instead of on the distance value gets the monotonicity wrong.
cnt += r - l, not r - l + 1 — a value is not paired with itself.
The count reaches about 5 · 10^7, which fits int but overflows a 16-bit accumulator.

Reference solution

Python

from typing import List

def smallestDistancePair(nums: List[int], k: int) -> int:
    s = sorted(nums)

    def count_le(d: int) -> int:
        cnt = 0
        l = 0
        for r in range(len(s)):
            while s[r] - s[l] > d:
                l += 1
            cnt += r - l
        return cnt

    lo, hi = 0, s[-1] - s[0]
    while lo < hi:
        mid = (lo + hi) // 2
        if count_le(mid) >= k:
            hi = mid
        else:
            lo = mid + 1
    return lo

JavaScript

var smallestDistancePair = function(nums, k) {
    var s = nums.slice().sort(function(a, b) { return a - b; });
    var countLE = function(d) {
        var cnt = 0, l = 0;
        for (var r = 0; r < s.length; r++) {
            while (s[r] - s[l] > d) l++;
            cnt += r - l;
        }
        return cnt;
    };
    var lo = 0, hi = s[s.length - 1] - s[0];
    while (lo < hi) {
        var mid = Math.floor((lo + hi) / 2);
        if (countLE(mid) >= k) hi = mid; else lo = mid + 1;
    }
    return lo;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue