#190HardBinary Search· Binary Search on Answer with Two Pointers

Kth Smallest Pair Gap

Sensors are mounted along a long pipeline at various positions (in metres), and several sensors can share the same position. For every pair of sensors the **gap** is the absolute difference of their positions. There are `n * (n - 1) / 2` pairs. Given the positions and an integer `k`, return the `k`-th smallest gap among all pairs (counting from 1, with equal gaps counted separately). Listing all pairs is too slow for large inputs, so find a better way.

Input format

`positions`: an array of integers; `k`: an integer.

Output format

An integer: the k-th smallest absolute difference over all unordered pairs of sensors.

Examples

Input: positions = [1, 3, 1], k = 1

Output: 0

The pair gaps are |1-3| = 2, |1-1| = 0 and |3-1| = 2. Sorted: 0, 2, 2. The 1st smallest is 0.

Input: positions = [1, 3, 1], k = 3

Output: 2

Sorted gaps are 0, 2, 2, so the 3rd smallest is 2.

Input: positions = [1, 6, 1], k = 2

Output: 5

The gaps are 5, 0 and 5, sorted 0, 5, 5. The 2nd smallest is 5.

Constraints

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

#binary-search
#two-pointers
#sorting
#binary-search-on-answer