#719

Hard

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Find K-th Smallest Pair Distance

Solve Find K-th Smallest Pair Distance by sorting nums, then binary searching the distance and counting valid pairs with two pointers.

array two pointers binary search sorting

Problem Statement

You are given an integer array nums and an integer k. For every pair of indices i and j with i < j, define the pair distance as the absolute difference between nums[i] and nums[j]. Your task is to return the k-th smallest distance among all possible pairs, so the answer depends on the ordering of distances, not on the ordering of the original elements.

A brute force approach would generate all pair distances, sort them, and pick the k-th one, but that breaks down because there are O(n^2) pairs. In this problem, the important structure is that pair distances fall inside a numeric range from 0 to max(nums) - min(nums), which makes it possible to search the answer space directly. For example, with nums = [1,3,1] and k = 1, the pair distances are 2, 0, and 2, so the smallest distance is 0.

Examples

Example 1

Input: nums = [1,3,1], k = 1

Output: 0

Here are all the pairs: (1,3) -> 2 (1,1) -> 0 (3,1) -> 2 Then the 1st smallest distance pair is (1,1), and its distance is 0.

Example 2

Input: nums = [1,1,1], k = 2

Output: 0

Example details omitted.

Example 3

Input: nums = [1,6,1], k = 3

Output: 5

Example details omitted.

Constraints

n == nums.length
2 <= n <= 104
0 <= nums[i] <= 106
1 <= k <= n * (n - 1) / 2

Solution Approach

Sort to make distance checks monotonic

Start by sorting nums. Once nums is sorted, increasing the right index only increases or preserves differences, which creates the monotonic condition needed for binary search on the answer. This step also turns the counting subproblem into a sliding-window scan instead of repeated absolute difference checks against unsorted values.

Binary search the distance, not the pair

Search between low = 0 and high = nums[n - 1] - nums[0]. For a guessed distance mid, ask a problem-specific question: how many index pairs have distance less than or equal to mid? If that count is at least k, then mid is large enough to cover the k-th smallest distance, so move left. Otherwise, move right. This works because the count of pairs with distance less than or equal to X never decreases as X grows.

Count pairs with a two-pointer window

Use two pointers on the sorted array to count pairs whose distance is at most mid. For each right index, advance left while nums[right] - nums[left] > mid. Then every index from left through right - 1 forms a valid pair with right, so add right - left to the count. A common failure mode here is resetting left for each right, which destroys the linear pass and misses the sorted-window advantage that makes this problem efficient.

Complexity Analysis

Metric	Value
Time	O(n \log M + n \log n)
Space	O(S)

Sorting costs O(n log n). Each binary search step performs one linear two-pointer count, and the search range spans distance values from 0 to M where M = max(nums) - min(nums), so the full runtime is O(n log n + n log M). The counting pass uses O(1) extra working space beyond the sort, so space is typically O(1) auxiliary, or O(log n) if you include sort stack usage depending on language implementation.

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

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

FAQ

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.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

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)

Continue Practicing

#658 find k closest elements #786 k th smallest prime fraction #825 friends of appropriate ages