Find K-th Smallest Pair Distance

LeetCode 719: Find K-th Smallest Pair Distance Solution & Explanation

Problem Overview

TL;DR: The optimal solution uses binary search on the answer (the distance value) combined with a sliding window approach to efficiently count pairs, avoiding the generation of all possible pairs.

The Find K-th Smallest Pair Distance problem asks us to determine the $k$-th smallest absolute difference between any two elements in a given integer array nums. If we were to calculate the absolute difference $|nums[i] - nums[j]|$ for every unique pair $(i, j)$ and sort these differences in ascending order, we need to return the value at the $(k-1)$-th index (0-indexed).

This is a classic "K-th value" problem that requires optimizing beyond simple enumeration, making LeetCode 719 a popular interview question for testing algorithm optimization skills.

Brute Force Approach for Find K-th Smallest Pair Distance

The most intuitive way to solve this problem is to generate every possible pair, calculate their distances, store them, and sort the results.

1. Initialize an empty list distances.
2. Iterate through the array with two loops: i from 0 to n-1 and j from i+1 to n-1.
3. Calculate abs(nums[i] - nums[j]) and append it to distances.
4. Sort the distances list.
5. Return the element at index k-1.

1# Pseudo-code for Brute Force
2def smallestDistancePair(nums, k):
3    distances = []
4    n = len(nums)
5    for i in range(n):
6        for j in range(i + 1, n):
7            distances.append(abs(nums[i] - nums[j]))
8    distances.sort()
9    return distances[k-1]

Why this fails: The time complexity of this approach is dominated by the number of pairs. For an array of size $N$, there are $N(N-1)/2$ pairs, which is $O(N^2)$. Sorting these pairs takes $O(N^2 \log(N^2))$. Given the constraint $N \le 10,000$, $N^2$ can reach $10^8$. Sorting $10^8$ elements will inevitably result in a Time Limit Exceeded (TLE) error. Additionally, storing all pairs consumes $O(N^2)$ memory, which may cause a Memory Limit Exceeded error.

Algorithm Strategy: Binary Search Patterns

1. Sort the Input: First, sort nums. This allows us to use a sliding window approach to count pairs and easily determine the maximum possible distance.
2. Define Search Space:
   • low = 0 (absolute difference is non-negative).
   • high = nums[n-1] - nums[0] (maximum possible difference).
3. Binary Search Loop:
   • While low < high:
     • Calculate mid = low + (high - low) // 2.
     • Count Pairs: Use a helper logic (Sliding Window) to count how many pairs $(i, j)$ satisfy nums[j] - nums[i] <= mid.
     • Adjust Bounds:
       • If count < k: We need more pairs, so the distance limit must be higher. Set low = mid + 1.
       • If count >= k: We have enough pairs. This mid could be the answer, or the answer could be smaller. Set high = mid.
4. Return: When low meets high, we have found the smallest distance for which there are at least k pairs. Return low.

Sliding Window Logic (The Counting Step): Since nums is sorted, for a fixed index right, as we decrease index left, the difference nums[right] - nums[left] increases. We want the smallest left such that nums[right] - nums[left] <= mid. All indices between left and right form valid pairs with right. The number of such pairs is right - left. We sum this for all right from 0 to n-1.

Execution Flow

Let nums = [1, 3, 1] and k = 1.

1. Preprocessing: Sort nums. New nums = [1, 1, 3].
2. Initialization:
   • low = 0
   • high = 3 - 1 = 2
3. Iteration 1:
   • mid = (0 + 2) // 2 = 1.
   • Count Pairs (<= 1):
     • right = 0 (val 1): left starts at 0. Diff 0 <= 1. Pairs: 0.
     • right = 1 (val 1): left is 0. Diff $1-1=0 \le 1$. Pairs += 1 - 0 = 1.
     • right = 2 (val 3): left moves to 2 (since $3-1 > 1$). Diff $3-3=0 \le 1$. Pairs += 2 - 2 = 0.
     • Total count = 1.
   • Check: Count (1) $\ge k$ (1). This distance is valid, but maybe a smaller one exists.
   • high = mid = 1.
4. Iteration 2:
   • low = 0, high = 1.
   • mid = (0 + 1) // 2 = 0.
   • Count Pairs (<= 0):
     • right = 0: Pairs += 0.
     • right = 1: $1-1=0 \le 0$. Pairs += 1.
     • right = 2: $3-1 > 0$, left moves to 2. Pairs += 0.
     • Total count = 1.
   • Check: Count (1) $\ge k$ (1).
   • high = mid = 0.
5. Termination:
   • low = 0, high = 0. Loop terminates.
   • Return 0.

Proof of Correctness

The correctness relies on the monotonicity of the problem. Let $f(d)$ be the number of pairs with distance less than or equal to $d$.

• If $d_1 < d_2$, then $f(d_1) \le f(d_2)$.
• We want the smallest $d$ such that $f(d) \ge k$.

Our binary search maintains the invariant that the answer lies within [low, high].

• If count(mid) < k, then mid is strictly too small. The answer must be $> mid$, so we set low = mid + 1.
• If count(mid) >= k, then mid is a potential candidate (it has enough pairs covering it), but there might be a smaller valid distance. We keep mid in the search space by setting high = mid.
• The loop terminates when low == high, converging on the smallest distance satisfying the condition.

Pattern Reuse Notes

The Binary Search Patterns applied here are highly versatile. The specific subpattern of searching the value space to find a K-th element appears in:

• LeetCode 4: Median of Two Sorted Arrays: Uses binary search on the partition cuts (indices) or values to handle two arrays simultaneously.
• LeetCode 378: Kth Smallest Element in a Sorted Matrix: Identical strategy. We binary search the value range of the matrix elements and count how many elements are $\le mid$ to determine rank.

Understanding LeetCode 719 solidifies the technique of "Binary Search on Answer," a powerful tool for optimization problems where the answer space is monotonic.

Reference Implementation

C++ Solution for LeetCode 719

1#include <vector>
2#include <algorithm>
3#include <cmath>
4
5class Solution {
6public:
7    int smallestDistancePair(std::vector<int>& nums, int k) {
8        std::sort(nums.begin(), nums.end());
9        
10        int n = nums.size();
11        int low = 0;
12        int high = nums[n - 1] - nums[0];
13        
14        while (low < high) {
15            int mid = low + (high - low) / 2;
16            
17            // Count pairs with distance <= mid
18            int count = 0;
19            int left = 0;
20            for (int right = 0; right < n; ++right) {
21                while (nums[right] - nums[left] > mid) {
22                    left++;
23                }
24                count += (right - left);
25            }
26            
27            // Binary Search Logic
28            if (count < k) {
29                low = mid + 1;
30            } else {
31                high = mid;
32            }
33        }
34        
35        return low;
36    }
37};

Java Solution for LeetCode 719

1import java.util.Arrays;
2
3class Solution {
4    public int smallestDistancePair(int[] nums, int k) {
5        Arrays.sort(nums);
6        
7        int n = nums.length;
8        int low = 0;
9        int high = nums[n - 1] - nums[0];
10        
11        while (low < high) {
12            int mid = low + (high - low) / 2;
13            
14            // Count pairs with distance <= mid
15            int count = 0;
16            int left = 0;
17            for (int right = 0; right < n; right++) {
18                while (nums[right] - nums[left] > mid) {
19                    left++;
20                }
21                count += (right - left);
22            }
23            
24            // Binary Search Logic
25            if (count < k) {
26                low = mid + 1;
27            } else {
28                high = mid;
29            }
30        }
31        
32        return low;
33    }
34}

Python Solution for LeetCode 719

1class Solution:
2    def smallestDistancePair(self, nums: List[int], k: int) -> int:
3        nums.sort()
4        
5        n = len(nums)
6        low = 0
7        high = nums[-1] - nums[0]
8        
9        while low < high:
10            mid = (low + high) // 2
11            
12            # Count pairs with distance <= mid
13            count = 0
14            left = 0
15            for right in range(n):
16                while nums[right] - nums[left] > mid:
17                    left += 1
18                count += (right - left)
19            
20            # Binary Search Logic
21            if count < k:
22                low = mid + 1
23            else:
24                high = mid
25                
26        return low