NeetCode #298LC-719HardBinary Search
← Back to All Problems#298 · #719 · Find K-th Smallest Pair Distance(找出第 K 小的数对距离)
📌 Problem Statement & Constraints
Given an integer array
nums and an integer k, return the k-th smallest distance among all pairs. The distance between a pair is the absolute difference of the two values. Constraints: 2 <= nums.length <= 10^4, 0 <= nums[i] <= 10^6, 1 <= k <= nums.length * (nums.length - 1) / 2.💡 Core Algorithmic Approaches
- Binary search on the distance
d: "are there at leastkpairs with distance at mostd" is monotone ind. - For a given
d, sort the array and use two pointers to count pairs with difference at mostdin O(n). - The count is accumulated as
r - lfor each right endpoint, which enumerates all valid pairs efficiently. - The search range is
[0, max(nums) - min(nums)].
💻 Benchmark Python3 Implementation
class Solution:
def smallestDistancePair(self, nums: List[int], k: int) -> int:
nums.sort()
def count(limit: int) -> int:
cnt = 0
l = 0
for r in range(len(nums)):
while nums[r] - nums[l] > limit:
l += 1
cnt += r - l # all pairs (l..r-1, r) qualify
return cnt
lo, hi = 0, nums[-1] - nums[0]
while lo < hi:
mid = (lo + hi) // 2
if count(mid) >= k:
hi = mid # enough pairs -> try a smaller distance
else:
lo = mid + 1
return lo⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n log n + n log(max distance)): the sort plus O(log V) counting passes, each O(n).
💾 Space Complexity
O(1) beyond the sort.
⚠️ Interview Pitfalls & Follow-ups
- Enumerating all pairs: O(n^2) with n = 10^4 gives 5 * 10^7 pairs -- borderline, and the binary search approach is O(n log V).
- Forgetting to sort: the two-pointer count requires sorted order.
- Using
hi = mid - 1when enough pairs exist: could skip the optimum. - Counting pairs with distance exactly
mid: the predicate is *at most*mid, which correctly handles duplicates in the distance multiset.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.