What is the main pattern in Find K-th Smallest Pair Distance?

The core pattern is binary search over the valid answer space. Instead of building all pair distances, you sort nums and test whether a candidate distance can cover at least k pairs.

Why does sorting help in this problem?

Sorting makes pair differences monotonic as the right pointer moves. That lets you count how many pairs have distance less than or equal to a guessed value in one linear scan.

How do you count pairs with distance <= X efficiently?

Use two pointers on the sorted array. For each right index, move left forward until nums[right] - nums[left] <= X, then add right - left valid pairs ending at right.

Why is brute force too slow for LeetCode 719?

There are O(n^2) pairs, so explicitly generating and sorting all distances becomes too expensive as n grows. The binary-search-plus-counting method avoids materializing that full distance list.

What usually goes wrong when implementing this solution?

Most bugs come from off-by-one updates in the binary search or from mismanaging the left pointer during counting. If the count function is not monotonic or linear, the whole approach breaks for this problem.

#719

Hard

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

找出第 K 小的数对距离

数对 (a,b) 由整数 a 和 b 组成，其数对距离定义为 a 和 b 的绝对差值。给你一个整数数组 nums 和一个整数 k ，数对由 nums[i] 和 nums[j] 组成且满足 0 。返回所有数对距离中第 k 小的数对距离。示例 1：输入： nums = [1,3,1], k =…

数组双指针二分查找排序

题目描述

数对 (a,b) 由整数 a 和 b 组成，其数对距离定义为 a 和 b 的绝对差值。

给你一个整数数组 nums 和一个整数 k ，数对由 nums[i] 和 nums[j] 组成且满足 0 <= i < j < nums.length 。返回 所有数对距离中 第 k 小的数对距离。

示例 1：

输入：nums = [1,3,1], k = 1
输出：0
解释：数对和对应的距离如下：
(1,3) -> 2
(1,1) -> 0
(3,1) -> 2
距离第 1 小的数对是 (1,1) ，距离为 0 。

示例 2：

输入：nums = [1,1,1], k = 2
输出：0

示例 3：

输入：nums = [1,6,1], k = 3
输出：5

提示：

n == nums.length
2 <= n <= 10⁴
0 <= nums[i] <= 10⁶
1 <= k <= n * (n - 1) / 2

lightbulb

解题思路

方法一：排序 + 二分查找

先对 $nums$ 数组进行排序，然后在 $[0, nums[n-1]-nums[0]]$ 范围内二分枚举数对距离 $dist$ ，若 $nums$ 中数对距离小于等于 $dist$ 的数量 $cnt$ 大于等于 $k$ ，则尝试缩小 $dist$ ，否则尝试扩大 $dist$ 。

时间复杂度 $O(nlogn×logm)$ ，其中 $n$ 表示 $nums$ 的长度， $m$ 表示 $nums$ 中两个数的最大差值。

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def smallestDistancePair(self, nums: List[int], k: int) -> int:
        def count(dist):
            cnt = 0
            for i, b in enumerate(nums):
                a = b - dist
                j = bisect_left(nums, a, 0, i)
                cnt += i - j
            return cnt

        nums.sort()
        return bisect_left(range(nums[-1] - nums[0]), k, key=count)

speed

复杂度分析

指标	值
时间	O(n \log M + n \log n)
空间	O(S)

psychology

面试官常问的追问

外企场景

question_mark
They hint to binary search the answer space instead of enumerating all pair distances.
question_mark
They ask how to count pairs with distance <= X efficiently after sorting.
question_mark
They push back on O(n^2) generation, which usually means the two-pointer counting check is the missing piece.

warning

常见陷阱

外企场景

error
Binary searching pair positions instead of binary searching the distance value itself.
error
Using a nested scan for each mid, which turns the counting check back into O(n^2).
error
Moving the left pointer incorrectly and undercounting or overcounting pairs when nums[right] - nums[left] exceeds mid.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Return the k-th largest pair distance, which flips how you reason about the count threshold.
arrow_right_alt
Count pairs with distance strictly less than X instead of less than or equal to X, which changes the boundary condition.
arrow_right_alt
Solve the same answer-space search when the array contains many duplicates, where zero-distance pairs dominate early ranks.

help

常见问题

外企场景

继续练习

#658 找到 K 个最接近的元素 #786 第 K 个最小的质数分数 #825 适龄的朋友