Find K-th Smallest Pair Distance

class Solution {
public:
    int smallestDistancePair(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        auto countLE = [&](int d) {
            int cnt = 0, l = 0;
            for (int r = 0; r < n; ++r) {
                while (nums[r] - nums[l] > d) ++l;
                cnt += r - l;
            }
            return cnt;
        };
        int lo = 0, hi = nums.back() - nums.front();
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (countLE(mid) < k) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }
};

import "sort"

func smallestDistancePair(nums []int, k int) int {
    sort.Ints(nums)
    n := len(nums)
    countLE := func(d int) int {
        cnt, l := 0, 0
        for r := 0; r < n; r++ {
            for nums[r]-nums[l] > d {
                l++
            }
            cnt += r - l
        }
        return cnt
    }
    lo, hi := 0, nums[n-1]-nums[0]
    for lo < hi {
        mid := lo + (hi-lo)/2
        if countLE(mid) < k {
            lo = mid + 1
        } else {
            hi = mid
        }
    }
    return lo
}

from typing import List

class Solution:
    def smallestDistancePair(self, nums: List[int], k: int) -> int:
        nums.sort()
        n = len(nums)

        def count_le(d: int) -> int:
            cnt = 0
            l = 0
            for r in range(n):
                while nums[r] - nums[l] > d:
                    l += 1
                cnt += r - l
            return cnt

        lo, hi = 0, nums[-1] - nums[0]
        while lo < hi:
            mid = lo + (hi - lo) // 2
            if count_le(mid) < k:
                lo = mid + 1
            else:
                hi = mid
        return lo

function smallestDistancePair(nums, k) {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    const countLE = (d) => {
        let cnt = 0, l = 0;
        for (let r = 0; r < n; r++) {
            while (nums[r] - nums[l] > d) l++;
            cnt += r - l;
        }
        return cnt;
    };
    let lo = 0, hi = nums[n - 1] - nums[0];
    while (lo < hi) {
        const mid = lo + ((hi - lo) >> 1);
        if (countLE(mid) < k) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

class Solution {
    public int smallestDistancePair(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length;
        int lo = 0, hi = nums[n - 1] - nums[0];
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (countLE(nums, mid) < k) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }

    private int countLE(int[] nums, int d) {
        int cnt = 0, l = 0;
        for (int r = 0; r < nums.length; r++) {
            while (nums[r] - nums[l] > d) l++;
            cnt += r - l;
        }
        return cnt;
    }
}

function smallestDistancePair(nums: number[], k: number): number {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    const countLE = (d: number): number => {
        let cnt = 0, l = 0;
        for (let r = 0; r < n; r++) {
            while (nums[r] - nums[l] > d) l++;
            cnt += r - l;
        }
        return cnt;
    };
    let lo = 0, hi = nums[n - 1] - nums[0];
    while (lo < hi) {
        const mid = lo + ((hi - lo) >> 1);
        if (countLE(mid) < k) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}