Watch 10 video solutions for Find K-th Smallest Pair Distance, a hard level problem involving Array, Two Pointers, Binary Search. This walkthrough by NeetCodeIO has 21,300 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
The distance of a pair of integers a and b is defined as the absolute difference between a and b.
Given an integer array nums and an integer k, return the kth smallest distance among all the pairs nums[i] and nums[j] where 0 <= i < j < nums.length.
Example 1:
Input: nums = [1,3,1], k = 1 Output: 0 Explanation: Here are all the pairs: (1,3) -> 2 (1,1) -> 0 (3,1) -> 2 Then the 1st smallest distance pair is (1,1), and its distance is 0.
Example 2:
Input: nums = [1,1,1], k = 2 Output: 0
Example 3:
Input: nums = [1,6,1], k = 3 Output: 5
Constraints:
n == nums.length2 <= n <= 1040 <= nums[i] <= 1061 <= k <= n * (n - 1) / 2Problem Overview: You receive an integer array nums and an integer k. Consider the absolute difference between every pair (i, j) where i < j. The task is to return the k-th smallest pair distance among all these differences.
Approach 1: Sort and Use a Min-Heap (O(n log n + k log n) time, O(n) space)
Start by sorting the array so pair distances become easier to manage. For each index i, the smallest distance involving that element is with i + 1. Push these initial pairs into a min-heap keyed by their distance. Each heap pop gives the next smallest distance. After removing a pair (i, j), push the next pair (i, j + 1) if it exists. This works similarly to merging sorted lists, where each row represents distances starting from the same element. Sorting costs O(n log n), and extracting k distances from the heap costs O(k log n). Useful when k is relatively small compared to the total number of pairs.
Approach 2: Binary Search on Distance + Two Pointers (O(n log n + n log W) time, O(1) space)
The key observation: instead of enumerating all pair distances, you can binary search the answer. The smallest possible distance is 0, and the largest is max(nums) - min(nums). After sorting the array, guess a distance mid and count how many pairs have distance ≤ mid. This counting step uses the two pointers technique: move a right pointer forward and advance the left pointer whenever the difference exceeds mid. Each step adds right - left valid pairs.
If the number of pairs ≤ mid is at least k, the k-th distance must be ≤ mid, so shrink the search range. Otherwise increase the distance. This binary search continues until the smallest feasible distance is found. The counting step runs in O(n), and the binary search runs log W iterations where W is the value range.
This approach avoids generating all O(n²) pairs. The array is sorted once using sorting, and every iteration efficiently counts valid pairs.
Recommended for interviews: Binary search on distance combined with two pointers is the expected solution. It demonstrates strong understanding of search space reduction and pair counting techniques. The heap approach proves you can model the problem with priority queues, but interviewers typically look for the binary search insight because it scales better for large arrays.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sort + Min-Heap | O(n log n + k log n) | O(n) | Good when k is relatively small and you want to generate distances in sorted order |
| Binary Search on Distance + Two Pointers | O(n log n + n log W) | O(1) | Best scalable solution for large arrays; common interview expectation |