719. Find K-th Smallest Pair Distance
Approach
Binary search on the distance; count pairs with distance ≤ m
using a two-pointer sliding window on the sorted array.
Key Techniques
Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.
The two-pointer technique places pointers at different positions (often the two ends) and moves them toward each other. It turns O(n²) nested loops into O(n) sweeps for problems like pair sums, removing duplicates, and container capacity. Works best on sorted or partitioned arrays.
Binary search reduces search space by half each step, giving O(log n) time. Beyond sorted arrays, apply it on the answer space ("binary search on result") when you can define a monotonic predicate — e.g., "can we achieve X with k resources?"
// Approach: Binary search on the distance; count pairs with distance ≤ m
// using a two-pointer sliding window on the sorted array.
// Time: O(n log n + n log W) Space: O(1)
public class Solution
{
public int SmallestDistancePair(int[] nums, int k)
{
Array.Sort(nums);
int l = 0;
int r = nums[nums.Length - 1] - nums[0];
while (l < r)
{
int m = (l + r) / 2;
if (numPairDistancesNoGreater(nums, m) >= k)
r = m;
else
l = m + 1;
}
return l;
}
private int numPairDistancesNoGreater(int[] nums, int m)
{
int count = 0;
int j = 1;
for (int i = 0; i < nums.Length; i++)
{
while (j < nums.Length && nums[j] <= nums[i] + m)
++j;
count += j - i - 1;
}
return count;
}
}