visual walkthrough
Find K-th Smallest Pair Distance
Combines search on answer with a two-pointer count.
The idea
There are n² pair distances, but you only need the kth smallest. Binary search the distance instead.
After sorting, the pairs within distance d are counted in one pass: for each right end, everything in the window from the first value ≥ right − d pairs with it.
Complexity
| approach | time | space |
|---|---|---|
| Every pair | O(n² log n) | O(n²) |
| Binary search + sliding window | O(n log n + n log W) | O(1) |