130. Find K-th Smallest Pair Distance

Given an integer array nums and integer k, return the k-th smallest distance among all pairs |nums[i]-nums[j]| (i<j). Input: '[nums], k'.

Input: '[nums], k'.

Output: Integer — k-th smallest distance.

Examples

Example 1

Input: [1,3,1], 1
Output: 0
Explanation: Distances {2,0,2}; sorted {0,2,2}; 1st is 0.

Example 2

Input: [1,1,1], 2
Output: 0
Explanation: All distances 0.

Example 3

Input: [1,6,1], 3
Output: 5
Explanation: Distances {5,0,5}; 3rd is 5.