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.

Examples