# Find K th Smallest Pair Distance

This page explains Java solution to problem `Find K th Smallest Pair Distance` using `Binary Search` algorithm.

## Problem Statement

Given an integer array, return the k-th smallest distance among all the pairs. The distance of a pair (A, B) is defined as the absolute difference between A and B.

Example 1:

Input: nums = [1,3,1] k = 1
Output: 0
Explanation:
Here are all the pairs:
(1,3) -> 2
(1,1) -> 0
(3,1) -> 2
Then the 1st smallest distance pair is (1,1), and its distance is 0.

## Solution

If you have any suggestions in below code, please create a pull request by clicking here.
``````
package com.vc.hard;

import java.util.Arrays;

class FindKThSmallestPairDistance {
public int smallestDistancePair(int[] nums, int k) {
Arrays.sort(nums);
int n = nums.length;
int lo = 0;
int hi = nums[n - 1] - nums;
while(lo < hi) {
int distance = lo + (hi - lo) / 2;
if(isDistanceIndexSmallerThanK(nums, distance, k)) lo = distance + 1;
else hi = distance;
}
return lo;
}

private boolean isDistanceIndexSmallerThanK(int[] nums, int distance, int k) {
int left = 0;
int count = 0;
for(int right = 0; right < nums.length; right++) {
while(nums[right] - nums[left] > distance) left++;
count += right - left;
}
return count < k;
}
}
``````

## Time Complexity

O(N log N + N * log D) Where
D is distance between smallest and largest element in an array
N is total number of elements in an input array

O(1)