Course4all
Join us on telegram
Home/dsa/Binary Search/Find K-th Smallest Pair Distance

Find K-th Smallest Pair Distance

Master this topic with zero to advance depth.

Find K-th Smallest Pair Distance

The distance of a pair of integers a and b is defined as the absolute difference between a and b. Given an integer array nums and an integer k, return the k-th smallest distance among all the pairs nums[i] and nums[j] where 0lei<j<N0 \\le i < j < N.

Hard

Examples

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

Level I: Brute Force (Iterate All Pairs)

Intuition

Calculate every possible pair distance, store them, and pick the kk-th smallest.

⏱ $O(N^2)$💾 $O(N^2)$

Detailed Dry Run

nums = [1,3,1], k=1 Distances: |1-3|=2, |1-1|=0, |3-1|=2. Sorted: [0, 2, 2]. Result: 0.

java
class Solution {
    public int smallestDistancePair(int[] nums, int k) {
        int n = nums.length, ds[] = new int[n * (n - 1) / 2], idx = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) ds[idx++] = Math.abs(nums[i] - nums[j]);
        }
        Arrays.sort(ds);
        return ds[k - 1];
    }
}
Approach 2

Level II: Min-Heap (Heap of Pairs)

Intuition

Sort the array. Adjacent pairs (i,i+1)(i, i+1) have the smallest gaps. Use a min-heap to explore larger gaps (i,j+1)(i, j+1) sequentially.

⏱ $O((N + K) \\log N)$💾 $O(N)$

Detailed Dry Run

nums=[1,1,3], k=1 Heap: (0,1) dist 0, (1,2) dist 2. Pop (0,1). Result 0.

java
class Solution {
    public int smallestDistancePair(int[] nums, int k) {
        Arrays.sort(nums);
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> (nums[a[1]]-nums[a[0]]) - (nums[b[1]]-nums[b[0]]));
        for (int i = 0; i < nums.length-1; i++) pq.offer(new int[]{i, i+1});
        for (int i = 0; i < k-1; i++) {
            int[] cur = pq.poll();
            if (cur[1]+1 < nums.length) pq.offer(new int[]{cur[0], cur[1]+1});
        }
        int[] res = pq.poll();
        return nums[res[1]] - nums[res[0]];
    }
}
Approach 3

Level III: Optimal (Binary Search + Sliding Window)

Intuition

Binary search for the distance DD such that there are at least kk pairs with distance leD\\le D. Counting is done in O(N)O(N) using two pointers.

⏱ $O(N \\log N + N \\log(Max))$💾 $O(1)$

Detailed Dry Run

nums=[1,1,3], k=1. Sorted: [1,1,3]. L=0, R=2. Mid=1. Count=2 >= 1. R=1. L=0, R=1. Mid=0. Count=1 >= 1. R=0. Result 0.

java
class Solution {
    public int smallestDistancePair(int[] nums, int k) {
        Arrays.sort(nums);
        int l = 0, r = nums[nums.length-1]-nums[0];
        while (l < r) {
            int mid = l + (r-l)/2;
            if (count(nums, mid) >= k) r = mid; else l = mid + 1;
        }
        return l;
    }
    int count(int[] nums, int d) {
        int c = 0, l = 0;
        for (int r = 0; r < nums.length; r++) {
            while (nums[r]-nums[l] > d) l++;
            c += r - l;
        }
        return c;
    }
}
← Previous QuestionMedian of Two Sorted Arrays
Next Question →Minimum Time to Complete Trips