bitonic-kth-pair-distance

Answer

Algorithm — O(n log(max-min)) time, O(1) extra space:

1. Sort the array (idempotent if already sorted).
2. Binary search on the answer d over [0, nums[n-1]-nums[0]]. The predicate is monotone: count(d) = #pairs with diff ≤ d is non-decreasing in d, so the smallest d with count(d) ≥ k is exactly the k-th smallest difference.
3. Two-pointer window count in O(n): for each right index, advance left until nums[right]-nums[left] ≤ d; every index in [left, right-1] pairs validly with right, so accumulate right - left. Duplicates are handled naturally (equal values contribute difference 0 and are counted like any other pair). count uses int64 so k up to n(n-1)/2 (≈ 5×10⁹ for n=10⁵) never overflows.

package kthpair

import "sort"

// KthSmallestPairDistance returns the k-th (1-indexed) smallest absolute
// difference among all pairs of nums (sorted in place).
func KthSmallestPairDistance(nums []int, k int) int {
    sort.Ints(nums)
    n := len(nums)
    if n < 2 {
        return 0
    }

    count := func(d int) int64 { // pairs with nums[j]-nums[i] <= d, O(n)
        var total int64
        left := 0
        for right := 0; right < n; right++ {
            for left < right && nums[right]-nums[left] > d {
                left++
            }
            total += int64(right - left)
        }
        return total
    }

    lo, hi := 0, nums[n-1]-nums[0]
    for lo < hi {
        mid := lo + (hi-lo)/2
        if count(mid) >= int64(k) {
            hi = mid
        } else {
            lo = mid + 1
        }
    }
    return lo
}

func TotalPairs(n int) int64 { return int64(n) * int64(n-1) / 2 }

Key correctness points: - Monotone predicate: if count(mid) < k, the answer is strictly greater than mid; otherwise the answer is ≤ mid. Standard lower-bound binary search. - Window count correctness: for fixed right, as left grows nums[right]-nums[left] shrinks; stopping at the first left with diff ≤ d means exactly right - left valid partners. Each left advances at most n times total → O(n) per count. - Duplicates: pairs of equal elements have difference 0; the count loop treats them as normal pairs (left < right guard), so all-equal arrays yield every difference 0. - Large k: int64 arithmetic for pair counts; k can equal n(n-1)/2 (the largest difference) and is handled by the same search.