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.

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

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)