Find K-th Smallest Pair Distance

Find K-th Smallest Pair Distance

What is this problem about?

The Find K-th Smallest Pair Distance interview question asks you to find the $k$-th smallest value among all absolute differences $|nums[i] - nums[j]|$ for every possible pair of indices $(i, j)$ in an array. For an array of size $n$, there are $n(n-1)/2$ such distances.

Why is this asked in interviews?

This "Hard" problem is a favorite at Google and Microsoft because it tests your ability to use Binary Search on the Answer. Since you can't generate all $O(n^2)$ distances, you must search for the distance value itself. It evaluations your mastery of combining binary search with the Two Pointers interview pattern to count pairs efficiently.

Algorithmic pattern used

This problem uses Binary Search on Value Range and Sliding Window (Two Pointers).

1. Sort the array first.
2. The search range for the distance is [0, max(nums) - min(nums)].
3. For a target distance mid, count how many pairs have a distance $\le mid$.
   • Use two pointers: for each right, find the smallest left such that nums[right] - nums[left] <= mid. All indices between left and right form valid pairs.
4. If the count is $\ge k$, mid could be the answer (try smaller). Otherwise, the answer must be larger.

Example explanation

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

1. Sorted: [1, 1, 3]. Range: [0, 2].
2. Try mid = 0: Pairs $\le 0$ is 1 (index 0 and 1). Count = 1.
3. Since $1 \ge k$, the answer is 0. (Actually, the binary search would continue to find the exact boundary).

Common mistakes candidates make

• $O(n^2)$ Pair Generation: Calculating all distances and sorting them, which results in Time Limit Exceeded.
• Incorrect counting: Using a nested loop for counting instead of the $O(n)$ two-pointers optimization.
• Search Range: Starting the binary search on indices instead of values.

Interview preparation tip

When asked for the "$k$-th" anything in a large combinatorial space, always check if you can solve the "Check(X): are there at least $k$ items smaller than X?" sub-problem efficiently. If you can, Binary Search on the Answer is the way to go.