⚡Flashcard Drill➔
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

  1. Binary search on the distance d: "are there at least k pairs with distance at most d" is monotone in d.
  2. For a given d, sort the array and use two pointers to count pairs with difference at most d in O(n).
  3. The count is accumulated as r - l for each right endpoint, which enumerates all valid pairs efficiently.
  4. 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 - 1 when 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.
🎯 Drill This Card Now➔

🧩 Related Binary Search Problems