hardBinary SearchPure DSA~45 min
Kth Smallest Pairwise Gap
Given timestamps of events, an anomaly detector ranks all pairwise time gaps. To set a threshold it needs the k-th smallest absolute gap among every pair of events.
Problem
Given an integer array nums, the distance of a pair (a, b) is |a − b|. Return the k-th smallest distance among all n·(n−1)/2 pairs.
Input
An array nums of n integers (2 ≤ n ≤ 10^4, 0 ≤ nums[i] ≤ 10^6) and an integer k.
Output
An integer: the k-th smallest pairwise absolute distance.
Constraints
- 2 ≤ n ≤ 10^4
- 1 ≤ k ≤ n·(n−1)/2
- Distances are absolute differences
Examples
Example 1
Input
nums = [1,3,1], k = 1
Output
0
Pairwise distances are {0,2,2}; the 1st smallest is 0.
Example 2
Input
nums = [1,6,1], k = 3
Output
5
Distances {0,5,5}; the 3rd smallest is 5.