# Find K-th Smallest Pair Distance
**Difficulty:** HARD
[External](https://leetcode.com/problems/find-k-th-smallest-pair-distance)
Canonical: https://scaleengineer.com/dsa/problems/find-k-th-smallest-pair-distance
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [Flipkart](https://scaleengineer.com/companies/flipkart), [Pinterest](https://scaleengineer.com/companies/pinterest)
---
## Problem
The **distance of a pair** of integers `a` and `b` is defined as the absolute difference between `a` and `b`.

Given an integer array `nums` and an integer `k`, return _the_ `kth` _smallest **distance among all the pairs**_ `nums[i]` _and_ `nums[j]` _where_ `0 <= i < j < nums.length`.

**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.

**Example 2:**

**Input:** nums = [1,1,1], k = 2
**Output:** 0

**Example 3:**

**Input:** nums = [1,6,1], k = 3
**Output:** 5

**Constraints:**

* `n == nums.length`
* `2 <= n <= 104`
* `0 <= nums[i] <= 106`
* `1 <= k <= n * (n - 1) / 2`

# Approaches
## Brute Force with Sorting
This approach involves generating all possible pair distances, storing them in a list, sorting the list, and then picking the k-th element. It is the most straightforward solution but also the least efficient.
**Time:** O(N^2 log(N^2)), which simplifies to O(N^2 log N). There are O(N^2) pairs to generate. Sorting a list of size O(N^2) takes O(N^2 log(N^2)) time. · **Space:** O(N^2), where N is the number of elements in `nums`. This is required to store all the pair distances in a list.
**Pros:** Simple to understand and implement.
**Cons:** Highly inefficient for large inputs due to its high time complexity.; Requires a large amount of memory to store all pair distances, which can lead to Memory Limit Exceeded errors.
### Explanation
The brute-force method is the most intuitive way to solve this problem. We simply follow the problem definition: find all pair distances, then find the k-th smallest among them.

The algorithm proceeds as follows:
1.  Initialize an empty list, for example, `distances`, to store the absolute differences between pairs of numbers.
2.  Use nested loops to iterate through all unique pairs of indices `(i, j)` where `i < j`.
3.  For each pair `(nums[i], nums[j])`, calculate the distance `d = Math.abs(nums[i] - nums[j])`.
4.  Add this distance `d` to the `distances` list.
5.  After iterating through all pairs, the `distances` list will contain all `N * (N - 1) / 2` pair distances.
6.  Sort the `distances` list in ascending order.
7.  The k-th smallest distance is the element at index `k - 1` of the sorted list.

```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public int smallestDistancePair(int[] nums, int k) {
        int n = nums.length;
        List<Integer> distances = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                distances.add(Math.abs(nums[i] - nums[j]));
            }
        }
        Collections.sort(distances);
        return distances.get(k - 1);
    }
}
```
This approach is simple but inefficient due to the large number of pairs, which can be up to approximately 5 * 10^7 for N = 10^4. Sorting this many elements is computationally expensive and will not pass the given constraints.
### Algorithm
- Initialize an empty list, `distances`.
- Use nested loops to iterate through all unique pairs of indices `(i, j)` where `i < j`.
- For each pair `(nums[i], nums[j])`, calculate the distance `d = Math.abs(nums[i] - nums[j])`.
- Add this distance `d` to the `distances` list.
- After iterating through all pairs, sort the `distances` list in ascending order.
- The k-th smallest distance is the element at index `k - 1` of the sorted list.

## Binary Search on the Answer with Two Pointers
This is a highly efficient approach that leverages the properties of the problem. Instead of finding the distances directly, we can binary search for the k-th smallest distance value. The key idea is to guess a distance `d` and then efficiently count how many pairs have a distance less than or equal to `d`.
**Time:** O(N log N + N log W), where N is the length of `nums` and W is the difference between the maximum and minimum values in `nums`. O(N log N) is for the initial sort. The binary search runs O(log W) times, and each time we do an O(N) scan (the `countPairs` function). · **Space:** O(log N) or O(N), depending on the implementation of the sorting algorithm. If we are allowed to modify the input array, it can be O(log N) for the recursion stack. Otherwise, O(N) for a copy.
**Pros:** Very efficient and passes the time limits for the given constraints.; It cleverly transforms the problem from finding an element to a decision problem, which is a common and powerful technique.
**Cons:** More complex to understand and implement compared to the brute-force approach.; Requires a good grasp of binary search on the answer and the two-pointer technique.
### Explanation
A much more efficient solution involves binary searching for the answer. The possible distances are bounded between 0 and `max(nums) - min(nums)`. We can binary search within this range. For any given distance `d`, we need to be able to efficiently count how many pairs have a distance less than or equal to `d`. If this count is at least `k`, then the k-th smallest distance is `d` or smaller. Otherwise, it must be larger than `d`.

The `countPairs` function, which counts pairs with distance `<= mid`, can be implemented efficiently using a two-pointer (or sliding window) approach on the sorted array in O(N) time.
- Initialize `count = 0` and a right pointer `right = 0`.
- Iterate with a left pointer `left` from `0` to `n-1`.
- For each `left`, advance `right` such that `nums[right] - nums[left] <= mid`.
- The number of valid pairs for the current `left` is `right - left - 1`. Add this to the total `count`.

```java
import java.util.Arrays;

class Solution {
    public int smallestDistancePair(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length;
        int low = 0;
        int high = nums[n - 1] - nums[0];
        int ans = 0;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            // Count pairs with distance <= mid
            if (countPairs(nums, mid) >= k) {
                ans = mid; // This is a potential answer
                high = mid - 1; // Try for a smaller distance
            } else {
                low = mid + 1; // Distance is too small
            }
        }
        return ans;
    }

    // Counts pairs with distance <= mid in O(N)
    private int countPairs(int[] nums, int mid) {
        int count = 0;
        int n = nums.length;
        int right = 0;
        for (int left = 0; left < n; ++left) {
            // While the condition is met, move the right pointer
            while (right < n && nums[right] - nums[left] <= mid) {
                right++;
            }
            // For nums[left], all elements from nums[left+1] to nums[right-1] form a valid pair.
            // The number of such elements is (right - 1) - (left + 1) + 1 = right - left - 1.
            count += right - left - 1;
        }
        return count;
    }
}
```
### Algorithm
- First, sort the input array `nums`.
- Define the search space for the binary search. The smallest possible distance is 0, and the largest is `nums[n-1] - nums[0]`. Let `low = 0` and `high = nums[n-1] - nums[0]`.
- Perform a binary search on the range `[low, high]`. For each `mid` value (a potential answer):
    - Count the number of pairs `(nums[i], nums[j])` with `nums[j] - nums[i] <= mid`. This can be done in O(N) time using a two-pointer/sliding window technique on the sorted array.
    - Let this count be `count`.
    - If `count >= k`, it means `mid` might be our answer, or the actual answer is even smaller. So, we record `mid` as a potential answer and try to find a smaller one by setting `high = mid - 1`.
    - If `count < k`, it means `mid` is too small to be the k-th distance. We need to look for a larger distance, so we set `low = mid + 1`.
- The last recorded potential answer will be the smallest distance `d` for which there are at least `k` pairs with distance `<= d`, which is the k-th smallest distance.

# Solutions
### Java

```java
class Solution {
public
  int smallestDistancePair(int[] nums, int k) {
    Arrays.sort(nums);
    int left = 0, right = nums[nums.length - 1] - nums[0];
    while (left < right) {
      int mid = (left + right) >> 1;
      if (count(mid, nums) >= k) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    return left;
  }
private
  int count(int dist, int[] nums) {
    int cnt = 0;
    for (int i = 0; i < nums.length; ++i) {
      int left = 0, right = i;
      while (left < right) {
        int mid = (left + right) >> 1;
        int target = nums[i] - dist;
        if (nums[mid] >= target) {
          right = mid;
        } else {
          left = mid + 1;
        }
      }
      cnt += i - left;
    }
    return cnt;
  }
}

```

### JavaScript

```javascript
/** * @param {number[]} nums * @param {number} k * @return {number} */ function smallestDistancePair(
  nums,
  k,
) {
  nums.sort((a, b) => a - b);
  const n = nums.length;
  let left = 0,
    right = nums[n - 1] - nums[0];
  while (left < right) {
    const mid = (left + right) >> 1;
    let count = 0,
      i = 0;
    for (let j = 0; j < n; j++) {
      while (nums[j] - nums[i] > mid) {
        i++;
      }
      count += j - i;
    }
    if (count >= k) {
      right = mid;
    } else {
      left = mid + 1;
    }
  }
  return left;
}

```

### CPP

```cpp
class Solution {
public:
  int smallestDistancePair(vector<int> &nums, int k) {
    sort(nums.begin(), nums.end());
    int left = 0, right = nums.back() - nums.front();
    while (left < right) {
      int mid = (left + right) >> 1;
      if (count(mid, k, nums) >= k)
        right = mid;
      else
        left = mid + 1;
    }
    return left;
  }
  int count(int dist, int k, vector<int> &nums) {
    int cnt = 0;
    for (int i = 0; i < nums.size(); ++i) {
      int target = nums[i] - dist;
      int j = lower_bound(nums.begin(), nums.end(), target) - nums.begin();
      cnt += i - j;
    }
    return cnt;
  }
};

```

### Python

```python
class Solution:
    def smallestDistancePair(self, nums: List[int], k: int) -> int: def count(dist): cnt = 0 for i, b in enumerate(nums): a = b - dist j = bisect_left(nums, a, 0, i) cnt += i - j return cnt nums . sort() return bisect_left(range(nums[- 1] - nums[0]), k, key=count)

```