We have an array of integers, and we need to consider every possible pair (i, j) where i < j. For each pair, we compute the absolute difference |nums[i] - nums[j]|. Among all these distances, we want the k-th smallest one.

Two details shape the solution. First, the number of pairs is n*(n-1)/2, which reaches about 50 million when n = 10^4. Storing all those distances and sorting them is expensive. Second, many pairs can share the same distance, so we want the k-th value in the full sorted list of all pair distances counted with duplicates, not the k-th distinct distance.

Sorting the array first makes the distances easier to reason about. Once nums is sorted, the distance between two elements depends only on their positions in sorted order: nums[j] - nums[i] for i < j is always non-negative, so the absolute value disappears, and elements that are close in sorted order have smaller distances.

Key Constraints:

Intuition

Do exactly what the problem says: compute the distance for every pair, collect all distances, sort them, and return the k-th one. With n up to 10^4 there are about 50 million pairs, so this is slow, but it establishes a correct baseline.

After sorting the input array, iterate over all pairs (i, j) with i < j. Because the array is sorted, the distance is nums[j] - nums[i] with no absolute value needed. Store all these distances in a list, sort the list, and return the element at index k-1.

Algorithm

Visualization and Code

This approach generates and sorts all pair distances, which is expensive in both time and space. The distances are bounded by 10^6, and the next approach uses that bound to replace the comparison sort with a counting step.

Intuition

The comparison sort over the distances costs O(n^2 log n), but the distances live in a bounded range. The maximum distance is max(nums) - min(nums), call it W. Create a frequency array of size W+1 where bucket[d] holds how many pairs have distance exactly d, then scan the buckets from 0 upward, accumulating counts until the running total reaches k.

This is a counting sort on the distances. It still generates all pairs in O(n^2), but it replaces the O(n^2 log n) sort with an O(W) scan.

Algorithm

Visualization and Code

This eliminates the comparison sort but still generates all n^2 pair distances, and W can be as large as 10^6. The next approach finds the k-th smallest distance without enumerating any pairs.

Intuition

Instead of generating all distances, this approach answers a different question: for a given distance d, how many pairs have distance <= d? Define countPairs(d) as that count. As d increases, more pairs qualify, so countPairs is non-decreasing: if 10 pairs have distance <= 5, at least 10 pairs have distance <= 6. That monotonicity lets us binary search for the smallest d where countPairs(d) >= k, and that d is the k-th smallest distance.

Counting pairs with distance <= d on a sorted array uses two pointers. For each element nums[j], the earlier elements nums[i] with i < j that satisfy nums[j] - nums[i] <= d are those with nums[i] >= nums[j] - d. In sorted order these form a contiguous range ending at j-1, so finding its start with a left pointer that only moves forward costs O(n) total across all j.

Algorithm

For the counting step:

Visualization and Code