# 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[0];
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

## Space Complexity

O(1)