Find K-th Smallest Pair Distance

Hard
775.

Find K-th Smallest Pair Distance

Find K-th Smallest Pair Distance is a hard coding problem on arrays, sorting and binary search, asked in Amazon, Google and Apple interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var smallestDistancePair = function(nums, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Find K-th Smallest Pair Distance — Problem & Solution

Find K-th Smallest Pair Distance solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Find K-th Smallest Pair Distance is a hard coding problem on arrays, sorting and binary search, asked in Amazon, Google and Apple interviews.

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

Hints for Find K-th Smallest Pair Distance

  1. Hint 1

    Materialising every distance is O(n²) — too many to sort at the upper limit.

  2. Hint 2

    Binary search the answer: for a candidate distance d, how many pairs are at most d apart?

  3. Hint 3

    On a sorted array that count is a two-pointer sweep, and it is non-decreasing in d.

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

  1. Sort nums. The candidate distances lie in [0, max - min].
  2. countLE(d): slide r forward, advancing l while s[r] - s[l] > d; each r contributes r - l pairs.
  3. 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

Java

public static int smallestDistancePair(int[] nums, int k) {
    int[] s = nums.clone();
    Arrays.sort(s);
    int lo = 0, hi = s[s.length - 1] - s[0];
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        int cnt = 0, l = 0;
        for (int r = 0; r < s.length; r++) {
            while (s[r] - s[l] > mid) l++;
            cnt += r - l;
        }
        if (cnt >= k) hi = mid; else lo = mid + 1;
    }
    return lo;
}

C++

int smallestDistancePair(vector<int>& nums, int k) {
    vector<int> s = nums;
    sort(s.begin(), s.end());
    int n = (int) s.size();
    int lo = 0, hi = s[n - 1] - s[0];
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        int cnt = 0, l = 0;
        for (int r = 0; r < n; r++) {
            while (s[r] - s[l] > mid) l++;
            cnt += r - l;
        }
        if (cnt >= 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms