Find K-th Smallest Pair Distance

Share

Given an integer array nums and integer k, return the kth smallest value of |nums[i] - nums[j]| for all pairs (i, j) with i < j.

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

Solution Approach

Sort array. Binary search on the answer (pair distance). Count pairs with distance <= mid using sliding window.

  • Sort nums. lo=0, hi=nums[n-1]-nums[0].
  • For mid: count pairs with distance <= mid using two pointers.
  • If count >= k: hi=mid. Else lo=mid+1.
Java
import java.util.Arrays;

class Solution {
    public int smallestDistancePair(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length, lo = 0, hi = nums[n-1] - nums[0];
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            int count = 0, left = 0;
            for (int right = 0; right < n; right++) {
                while (nums[right] - nums[left] > mid) left++;
                count += right - left;
            }
            if (count >= k) hi = mid;
            else lo = mid + 1;
        }
        return lo;
    }
}
  • Time Complexity: O(N log N + N log W) where W=max distance
  • Space Complexity: O(1)