#include <algorithm>
#include <vector>

#include <iostream>

using std::sort;
using std::vector;

using std::cout; using std::endl;

class Solution {
public:
    int smallestDistancePair(vector<int>& nums, int k) {
        int len = nums.size();
        sort(nums.begin(), nums.end());
        int beg = 0, end = nums.back() - nums.front();
        while (beg < end) {
            int mid = beg + (end - beg) / 2;
            if (k <= pairs_less_than_or_equal(nums, mid)) {
                end = mid;
            } else {
                beg = mid + 1;
            }
        }
        return beg;
    }
private:
    int pairs_less_than_or_equal(vector<int>& nums, int d) {
        int len = nums.size();
        int cnt = 0;
        for (int i = 1, j = 0; i < len; i++) {
            while (j < i && d < nums[i] - nums[j])
                j++;
            cnt += i - j;
        }
        return cnt;
    }
};

int main() {
    Solution* sol = new Solution;

    vector<int> nums{1, 3, 1};
    int k = 1;

    cout << sol->smallestDistancePair(nums, k) << endl;

    return 0;
}