Given an integer array nums and an integer k, you are asked to find the k-th smallest distance among all possible pairs in the array. The distance between a pair (A, B) is defined as |A - B|, the absolute difference between their values. You must return the k-th smallest value among all these pairwise distances.
i and j (i < j).
nums.
Example:
Input: nums = [1,3,1], k = 1
Output: 0
Explanation: The possible pairs are (1,3), (1,1), (3,1). Their distances are 2, 0, 2. The 1st smallest distance is 0.
At first glance, the problem appears to require generating all possible pairs, calculating their distances, sorting these distances, and then returning the k-th smallest. However, this brute-force approach is inefficient for large arrays, as the number of pairs grows quadratically with the array size (O(n^2)).
To optimize, we need to avoid explicitly creating every pair. Noticing that the distance only depends on the values, and that sorting the array makes the smallest distances appear between close indices, hints at a more efficient approach. We can leverage sorting and binary search to quickly home in on the k-th smallest distance without generating all pairs.
The key insight is: For any given distance d, can we count how many pairs have distance ≤ d? If yes, we can use binary search to find the minimal distance for which this count is at least k.
We use a combination of sorting, binary search, and a two-pointer technique to efficiently solve the problem.
nums: Sorting ensures that for any two indices i < j, the distance nums[j] - nums[i] is non-negative and increases as j increases.
0 (minimum possible) to max(nums) - min(nums) (maximum possible distance). We perform binary search over this range to find the smallest distance d such that there are at least k pairs with distance ≤ d.
mid, we count the number of pairs with distance ≤ mid using a two-pointer technique:
i, move a pointer j as far right as possible such that nums[j] - nums[i] ≤ mid.i is j - i - 1 (since j is exclusive).i to get total pairs with distance ≤ mid.k, increase the lower bound (search for larger distances).k, decrease the upper bound (search for smaller distances).This approach avoids generating all pairs and is much more efficient for large arrays.
Let's walk through the sample input: nums = [1,3,1], k = 1.
nums: [1,1,3]
low = 0, high = 2 (max distance)
mid = 1
high = 1
mid = 0
low = 1
low == high == 1, so the answer is 1.
However, this seems off; let's re-express the count for mid = 0:
mid = 0, count = 1, so high = 0.
When low == high == 0, the answer is 0, which is correct.
This process efficiently finds the k-th smallest distance without generating all pairs.
O(n^2 \log n) (generate all pairs, sort distances)O(n^2) (store all pairwise distances)O(n \log D), where D is the range of possible distances (max-min). For each binary search step, counting pairs takes O(n).O(1) (ignoring the sorting step, or O(n) for sorting)The optimized approach is much more efficient, especially for large arrays.
class Solution:
def smallestDistancePair(self, nums: List[int], k: int) -> int:
nums.sort()
n = len(nums)
def count_pairs(mid):
count = left = 0
for right in range(n):
while nums[right] - nums[left] > mid:
left += 1
count += right - left
return count
low, high = 0, nums[-1] - nums[0]
while low < high:
mid = (low + high) // 2
if count_pairs(mid) < k:
low = mid + 1
else:
high = mid
return low
class Solution {
public:
int smallestDistancePair(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
int n = nums.size();
int low = 0, high = nums[n - 1] - nums[0];
while (low < high) {
int mid = (low + high) / 2;
int count = 0, left = 0;
for (int right = 0; right < n; ++right) {
while (nums[right] - nums[left] > mid)
++left;
count += right - left;
}
if (count < k)
low = mid + 1;
else
high = mid;
}
return low;
}
};
class Solution {
public int smallestDistancePair(int[] nums, int k) {
Arrays.sort(nums);
int n = nums.length;
int low = 0, high = nums[n - 1] - nums[0];
while (low < high) {
int mid = (low + high) / 2;
int count = 0, left = 0;
for (int right = 0; right < n; ++right) {
while (nums[right] - nums[left] > mid) {
++left;
}
count += right - left;
}
if (count < k) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}
}
var smallestDistancePair = function(nums, k) {
nums.sort((a, b) => a - b);
let n = nums.length;
let low = 0, high = nums[n - 1] - nums[0];
while (low < high) {
let mid = Math.floor((low + high) / 2);
let count = 0, left = 0;
for (let right = 0; right < n; ++right) {
while (nums[right] - nums[left] > mid) {
left++;
}
count += right - left;
}
if (count < k) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
};
The k-th smallest pair distance problem, while seemingly brute-force, can be solved efficiently by combining sorting, binary search, and a two-pointer counting technique. The main insight is to avoid generating all pairs by counting how many pairs have distances within a given threshold and using this in a binary search. This approach reduces time complexity from quadratic to nearly linear and demonstrates the power of algorithmic thinking and pattern recognition.