algo-kth-smallest-pair-distance
The naive approach enumerates all n(n−1)/2 pairs in O(n²) — impossible for n = 10⁵. The fix uses sort + binary search on the answer + O(n) two-pointer counting:
nums (O(n log n)). Now every pair distance is nums[j] - nums[i] for i < j.[0, max-min] (O(log W), W ≤ 10⁶).count(mid) ≥ k is monotonic, so the smallest mid satisfying it is the k-th smallest distance.i, advance a right pointer j while nums[j]-nums[i] ≤ mid. Since j only moves forward across all i, it's amortized O(n). Every index in i+1..j-1 forms a valid pair with i, so add j-i-1.import "sort"
func smallestDistancePair(nums []int, k int) int {
n := len(nums)
if n < 2 {
return 0
}
sort.Ints(nums)
countPairs := func(d int) int { // pairs with distance <= d, O(n)
cnt := 0
j := 0
for i := 0; i < n; i++ {
for j < n && nums[j]-nums[i] <= d {
j++
}
cnt += j - i - 1
}
return cnt
}
lo, hi := 0, nums[n-1]-nums[0]
for lo < hi {
mid := lo + (hi-lo)/2
if countPairs(mid) >= k {
hi = mid
} else {
lo = mid + 1
}
}
return lo
}
Total complexity: O(n log n + n log W) time, O(log n) stack for sort, O(1) extra space.
Verified in Go 1.26 with `go vet`, `-race`, and a test suite at `/tmp/kthdist`: - **`TestExamples` (10 cases, all pass)**: `[1,3,1] k=1→0, k=2→2, k=3→2`; `[1,1,1]` all distances 0; `[1,2,3,4] k=1→1, k=6→3`; extremes `[0,1000000] k=1→1000000`; `[5,5,5,5] k=6→0`. - **`TestRandomAgainstBrute` (2000 cases, pass)**: 2000 random arrays (n up to 40, values up to 10⁶) with random k compared against a brute-force O(n²) reference — zero mismatches. - **`TestLargestInput` (pass)**: n = 100 000, checked k = 1, k = total/2, k = total. For k = total the result must equal `max-min` of the sorted array — verified. All-equal array with k=1 returns 0. - **Performance**: benchmark on n = 10⁵ runs in **~4.4 ms/op** on this machine — the O(n²) approach would take minutes. Edge cases covered: single-element input (guarded), duplicate values (distance 0), k = n(n−1)/2 (largest distance), k = 1 (smallest distance), all-equal arrays.
{"model": "deepseek-v4-flash", "problem_class": "algo-kth-smallest-pair-distance", "result": "passed", "tests": 2015}