528. Find K-th Smallest Pair Distance

Given an array, the distance of a pair is the absolute difference of its two elements. Return the k-th smallest distance among all pairs. Use binary search on the distance with a two-pointer count. Input: '[arr], k'.

Input: '[arr], k'.

Output: Integer — the k-th smallest pair distance.

Examples

Input: [1,3,1], 1
Output: 0
Explanation: Smallest distance is 0 (the two 1s).

Input: [1,1,1], 2
Output: 0
Explanation: All pairs have distance 0.

Input: [1,6,1], 3
Output: 5
Explanation: 3rd smallest distance is 5.

Constraints

• 2<=n<=10^4
• 0<=value<=10^6
• 1<=k<=n*(n-1)/2

Asked by