Find the smallest number ans such that ans is not smaller than at least k differences. For each test value of ans, counting the number of differences not more than ans is done in linear time using two pointer method.

```
class Solution {
public:
int smallestDistancePair(vector<int>& a, int k) {
sort(a.begin(), a.end());
int n = a.size(), lo = 0, hi = a[n-1] - a[0], ans = -1;
while (lo <= hi) {
int cnt = 0, j = 0, md = (lo + hi)/2;
for (int i = 0; i < n; ++i) {
while (j < n && a[j] - a[i] <= md) ++j;
cnt += j - i-1;
}
if (cnt >= k) {
ans = md;
hi = md - 1;
}
else lo = md + 1;
}
return ans;
}
};
```