Solution: Find K-th Smallest Pair Distance

Statement

Given an array of integers nums and an integer k, return the $k^{th}$ smallest distance between any pair of integers (nums[i], nums[j]), where $0 \leq$ i $<$ j $<$ num.length.

The distance between a pair of integers, $a$ and $b$, is defined as the absolute difference between them.

Constraints:

• $n ==$ nums.length

• $2 \leq n \leq 10^3$

• $0 \leq$ nums[i] $\leq 10^3$

• $1 \leq$ k $\leq \frac{n \times (n-1)}{2}$

Note: Given an array of size $n$, the total number of possible pairs is given by ${}^{n}C_{2}$. As ${}^{n}C_{2}$ evaluates to $\frac{n \times (n-1)}{2}$, there are exactly these much possible $k$-distances.

Solution

We use a combination of binary search and the sliding window technique to develop an optimal solution to this problem. First, we sort the array and then apply binary search to find the $k^{th}$ smallest distance between pairs in the sorted array. The core idea is to iteratively narrow the binary search range for pair distances. At each step, a helper function uses the sliding window technique to count how many pairs have a distance less than or equal to the current midpoint. We adjust the binary search range based on whether the count is less than or greater than k. When the binary search range converges, we get the $k^{th}$ smallest distance.

Given a distance d, the helper function counts the number of pairs with a distance $\leq$ d. It uses the sliding window technique with two pointers, left and right. The right pointer iterates through the array and the left pointer increments only when the difference between the elements at the two pointers exceeds d. The number of valid pairs is calculated using right - left, as the pointers are maintained such that the difference between the two elements is always $\leq$ d. If the difference between the elements at right and left is $\leq$ d, then the difference between any two elements within the range bounded by these pointers will also be $\leq$ d because the array is sorted.

Using the above intuition, we implement the smallestDistancePair function as follows:

1. The first step is to sort the array nums.

   1. Sorting helps calculate pairwise distances in increasing order easily. After sorting, the smallest distance between any two elements will always be between adjacent elements.

2. Define the binary search range using the variables low and high:

   1. Initialize low with 0.

   2. Initialize high with nums[nums.length - 1] - nums[0] representing the largest possible distance between the smallest and largest elements.

3. Use binary search to find the smallest distance. The search continues as long as the low is smaller than the high:

   1. Calculate the midpoint, mid, which represents a potential candidate for the $k^{th}$ smallest distance. The goal is to find the smallest distance for which there are at least k pairs.

   2. For each midpoint mid, we count how many pairs have a distance less than or equal to mid using the helper function countPairsWithDistance.

   3. After counting the pairs, adjust the binary search range:

      1. If the count is less than k, we increase low to mid + 1.

      2. If the count is greater than or equal to k, we decrease high to mid.

4. Return low as the $k^{th}$ smallest distance when the binary search terminates.

The helper function countPairsWithDistance uses the sliding window technique to count the number of valid pairs. It takes the value mid from the smallestDistancePair function as its parameter (denoted as d) and is implemented as follows:

1. Initialize count with 0.

2. Initialize two pointers, left and right, with 0.

3. Iterate through the array using the right pointer and check how many pairs with the current right element have a distance less than or equal to d.

   1. While nums[right] - nums[left] > d, it means the pair (nums[left], nums[right]) is too far apart, so the left pointer is incremented to reduce the distance.

   2. The number of valid pairs with the right is then right - left, which is added to count.

Let’s look at the following illustration to get a better understanding of the solution: