719. Find K-th Smallest Pair Distance

    int smallestDistancePair(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int lo = 0, hi = nums.back() - nums.front(), mid;
        while(lo<hi) {
            mid = (lo + hi)/2;
            // count number of distances that is <= mid;
            int cnt = countDist(nums, mid);
            if(cnt >= k) hi = mid;
            else lo = mid + 1;
        }
        return lo;
    }
    int countDist(vector<int>& n, int dist) {
        int i = 0, j = 0, cnt = 0;
        for(; i < n.size(); i++) {
            while(j<n.size() && n[j] - n[i] <= dist) j++;
            cnt += j - i -1;
        }
        return cnt;
    }