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.

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.