LeetCode 719 - Find K-th Smallest Pair Distance

This problem asks us to find the k-th smallest distance among every possible pair of numbers in the array. For any pair (a, b), the distance is defined as: We are given an array nums, and we must consider every pair (nums[i], nums[j]) where i < j.

leetcodehardarraytwo-pointersbinary-searchsorting

LeetCode Problem 719

Difficulty: 🔴 Hard
Topics: Array, Two Pointers, Binary Search, Sorting

Solution

Problem Understanding

This problem asks us to find the k-th smallest distance among every possible pair of numbers in the array.

For any pair (a, b), the distance is defined as:

$|a-b|$

We are given an array nums, and we must consider every pair (nums[i], nums[j]) where i < j. For each pair, we compute the absolute difference between the two values. After collecting all pair distances, we sort them in ascending order and return the k-th smallest one.

For example, if:

nums = [1,3,1]

The pairs are:

(1,3) -> 2
(1,1) -> 0
(3,1) -> 2

The sorted distances become:

[0,2,2]

So the 1st smallest distance is 0.

The constraints are important:

  • 2 <= n <= 10^4
  • 0 <= nums[i] <= 10^6

The total number of pairs can be:

$\frac{n(n-1)}{2}$

When n = 10^4, this is roughly 50 million pairs, which is far too many to generate and sort directly in an efficient solution.

This immediately tells us that a naive brute-force approach will likely exceed time or memory limits. We need a more efficient strategy that avoids explicitly constructing all pair distances.

Several edge cases are especially important:

  • Arrays with many duplicate values, because distance 0 may appear many times.
  • Arrays where all numbers are identical.
  • Arrays where all numbers are far apart.
  • Large arrays where generating all pairs is impossible.
  • Cases where the answer is 0.
  • Cases where the answer is the maximum possible difference.

The problem guarantees valid input sizes and guarantees that k is always within the total number of possible pairs.

Approaches

Brute Force Approach

The most direct solution is to generate every pair (i, j) where i < j, compute the absolute difference, store all distances in an array, sort the array, and return the k - 1 indexed element.

This works because it literally constructs the complete list of pair distances, so after sorting we can directly access the desired order statistic.

However, the number of pairs is:

$\frac{n(n-1)}{2}$

For n = 10^4, this becomes about 50 million distances. Storing and sorting that many values is extremely expensive.

The brute-force solution therefore becomes impractical for the given constraints.

Optimal Approach

The key observation is that we do not actually need to generate all pair distances.

Instead, we can binary search the answer itself.

The smallest possible distance is:

0

The largest possible distance is:

max(nums) - min(nums)

Suppose we guess some distance mid.

We can then ask:

How many pairs have distance <= mid?

If there are at least k such pairs, then the answer must be <= mid.

Otherwise, the answer must be larger than mid.

This creates a monotonic property:

  • Small distance thresholds produce fewer valid pairs.
  • Larger distance thresholds produce more valid pairs.

Because of this monotonic behavior, binary search becomes possible.

The remaining challenge is efficiently counting how many pairs have distance <= mid.

After sorting the array, we can use a sliding window / two-pointer technique:

  • Expand the right pointer.
  • Move the left pointer whenever the distance becomes too large.
  • For each right pointer, count how many valid left positions exist.

This lets us count pairs in linear time for each binary search step.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n² log n²) O(n²) Generates and sorts all pair distances
Optimal O(n log n + n log W) O(1) extra Binary search on answer with two pointers

Here, W is the range of values:

max(nums) - min(nums)

Algorithm Walkthrough

  1. Sort the array.

Sorting is essential because the two-pointer counting technique relies on ordered values. Once sorted, pair distances become easier to reason about because increasing indices also increases values. 2. Define the binary search range.

The smallest possible distance is 0.

The largest possible distance is:

$\max(nums)-\min(nums)$

We binary search within this range. 3. Pick a middle distance mid.

This represents a candidate answer. 4. Count how many pairs have distance <= mid.

Use two pointers:

  • Maintain a left pointer left.
  • Iterate right from left to right.
  • While:
nums[right] - nums[left] > mid

move left forward.

After adjustment, every index between left and right - 1 forms a valid pair with right.

The number of new valid pairs is:

right - left
  1. Compare the count with k.
  • If the count is at least k, then mid could be the answer, or the answer could be smaller.
  • Otherwise, the answer must be larger.
  1. Continue binary search until the search range collapses.
  2. Return the final value.

Why it works

The correctness depends on a monotonic property.

Define:

f(d) = number of pairs with distance <= d

As d increases, f(d) never decreases.

Therefore, there exists a boundary where the number of valid pairs first becomes at least k. That boundary is exactly the k-th smallest pair distance.

Binary search correctly finds this boundary.

The sliding window counting method is correct because, after sorting, if:

nums[right] - nums[left] <= mid

then every index between left and right also satisfies the condition.

Python Solution

from typing import List

class Solution:
    def smallestDistancePair(self, nums: List[int], k: int) -> int:
        nums.sort()

        def count_pairs(max_distance: int) -> int:
            count = 0
            left = 0

            for right in range(len(nums)):
                while nums[right] - nums[left] > max_distance:
                    left += 1

                count += right - left

            return count

        low = 0
        high = nums[-1] - nums[0]

        while low < high:
            mid = (low + high) // 2

            if count_pairs(mid) >= k:
                high = mid
            else:
                low = mid + 1

        return low

The implementation begins by sorting the array. This allows pair distances to behave monotonically as indices increase.

The nested count_pairs function computes how many pairs have distance less than or equal to a given threshold. It uses a sliding window with two pointers.

The right pointer expands through the array. Whenever the distance becomes too large, the left pointer moves forward until the window becomes valid again.

For each right, every index from left through right - 1 forms a valid pair. Therefore, we add right - left to the count.

The outer binary search repeatedly tests candidate distances. If enough valid pairs exist, we search smaller distances. Otherwise, we search larger distances.

Eventually, low converges to the smallest distance whose count is at least k, which is the answer.

Go Solution

package main

import (
	"sort"
)

func smallestDistancePair(nums []int, k int) int {
	sort.Ints(nums)

	countPairs := func(maxDistance int) int {
		count := 0
		left := 0

		for right := 0; right < len(nums); right++ {
			for nums[right]-nums[left] > maxDistance {
				left++
			}

			count += right - left
		}

		return count
	}

	low := 0
	high := nums[len(nums)-1] - nums[0]

	for low < high {
		mid := (low + high) / 2

		if countPairs(mid) >= k {
			high = mid
		} else {
			low = mid + 1
		}
	}

	return low
}

The Go implementation follows the same algorithmic structure as the Python version.

Go uses sort.Ints(nums) for sorting. The counting logic is implemented with an anonymous function closure.

Integer overflow is not a concern here because the maximum distance is at most 10^6, well within Go's integer range.

Slices are used directly, and no additional large memory allocations are required.

Worked Examples

Example 1

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

Step 1: Sort

[1,1,3]

Binary Search State

low high mid
0 2 1

Now count pairs with distance <= 1.

Sliding Window

right nums[right] left after adjustment new pairs total
0 1 0 0 0
1 1 0 1 1
2 3 2 0 1

We found 1 valid pair.

Since count >= k, search left half.

low high
0 1

Next:

low high mid
0 1 0

Count pairs with distance <= 0.

right nums[right] left new pairs total
0 1 0 0 0
1 1 0 1 1
2 3 2 0 1

Again count is 1.

Search left half:

high = 0

Binary search ends.

Answer:

0

Example 2

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

Sorted array:

[1,1,1]

All pair distances are:

0,0,0

Binary search range:

low = 0
high = 0

The search immediately terminates.

Answer:

0

Example 3

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

Sorted:

[1,1,6]

Pair distances:

0,5,5

The 3rd smallest distance is:

5

Binary search eventually converges to 5.

Complexity Analysis

Measure Complexity Explanation
Time O(n log n + n log W) Sorting plus binary search with linear counting
Space O(1) extra Only pointers and counters are used

The sorting step costs O(n log n).

The binary search operates over the distance range W, where:

$W=\max(nums)-\min(nums)$

Each binary search iteration performs a linear scan using two pointers, giving O(n) work per iteration.

Since binary search performs O(log W) iterations, the total complexity becomes:

$O(n\log n+n\log W)$

The algorithm uses constant extra memory beyond the sorting implementation.

Test Cases

from typing import List

class Solution:
    def smallestDistancePair(self, nums: List[int], k: int) -> int:
        nums.sort()

        def count_pairs(max_distance: int) -> int:
            count = 0
            left = 0

            for right in range(len(nums)):
                while nums[right] - nums[left] > max_distance:
                    left += 1

                count += right - left

            return count

        low = 0
        high = nums[-1] - nums[0]

        while low < high:
            mid = (low + high) // 2

            if count_pairs(mid) >= k:
                high = mid
            else:
                low = mid + 1

        return low

sol = Solution()

assert sol.smallestDistancePair([1,3,1], 1) == 0  # example 1
assert sol.smallestDistancePair([1,1,1], 2) == 0  # all duplicates
assert sol.smallestDistancePair([1,6,1], 3) == 5  # example 3

assert sol.smallestDistancePair([1,2], 1) == 1  # minimum size array
assert sol.smallestDistancePair([1,1,2], 2) == 1  # duplicate handling
assert sol.smallestDistancePair([1,2,3,4], 1) == 1  # smallest distance
assert sol.smallestDistancePair([1,2,3,4], 6) == 3  # largest distance
assert sol.smallestDistancePair([0,1000000], 1) == 1000000  # maximum value range
assert sol.smallestDistancePair([4,4,4,4], 5) == 0  # many zero distances
assert sol.smallestDistancePair([1,3,7,10], 4) == 6  # mixed distances

Test Summary

Test Why
[1,3,1], k=1 Validates basic example
[1,1,1], k=2 Ensures duplicate distances work
[1,6,1], k=3 Validates larger distance result
[1,2], k=1 Smallest valid input size
[1,1,2], k=2 Checks duplicate and non-duplicate mix
[1,2,3,4], k=1 Finds smallest possible pair distance
[1,2,3,4], k=6 Finds largest possible pair distance
[0,1000000], k=1 Tests maximum numeric range
[4,4,4,4], k=5 Many identical values
[1,3,7,10], k=4 General mixed-distance scenario

Edge Cases

One important edge case occurs when many elements are identical. In such cases, many pair distances become 0. A buggy implementation might incorrectly count duplicate pairs or mishandle the sliding window boundaries. This solution handles duplicates naturally because sorted equal values remain adjacent, and the two-pointer counting logic correctly includes every valid pair.

Another important case is when the array has only two elements. There is exactly one possible pair, so the answer must be the absolute difference between those two numbers. The implementation handles this correctly because the binary search range collapses immediately to the only valid distance.

A third critical edge case involves extremely large value ranges, such as [0, 1000000]. Even though the numeric range is large, the binary search only performs logarithmic iterations over the range. The algorithm therefore remains efficient and avoids constructing huge intermediate structures.

A fourth subtle case happens when the k-th smallest distance appears multiple times. For example:

[1,1,1,2]

contains several identical distances. The binary search correctly finds the smallest distance whose cumulative pair count reaches at least k. This ensures duplicates are handled correctly and the exact order statistic is returned.