Find K-th Smallest Pair Distance

Hard

The distance of a pair (a, b) is |a - b|. Given an integer array nums and an integer k, return the k-th smallest distance among all n * (n - 1) / 2 pairs (1-indexed).

Example 1

Input:  nums = [1,3,1], k = 1
Output: 0

Example 2

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

Example 3

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

Constraints

• 2 <= nums.length <= 10^4
• 0 <= nums[i] <= 10^6
• 1 <= k <= n * (n - 1) / 2