Question:
This is a problem from LeetCode:
Given an integer array, return the k-th smallest distance among all the pairs. The distance of a pair (A, B) is defined as the absolute difference between A and B.
Example:
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.
My Problem
I solved it with a naive approach O(n^2) basically I find all distances and sort it then find the kth smallest. Now here is a better Solution. It is not my code I found it on the discussion forum on leetcode. But I am having trouble understanding a crucial part of the code.
The code below is basically doing a binary search. the low is the min distance and high is the max distance. calculate a mid like usual binary search. then it does countPairs(a, mid) to find number of pairs with absolute difference less than or equal to mid. then adjust low and high accordingly.
But WHY the binary Search result MUST be one of the distances? At first, low and high are got from the array, but the mid, is calculated by them, it may not be the distance. In the end we are returning low which the values changes during the binary search base on mid + 1. Why is mid + 1 guarantee to be one of the distance?
class Solution {
// Returns index of first index of element which is greater than key
private int upperBound(int[] a, int low, int high, int key) {
if (a[high] <= key) return high + 1;
while (low < high) {
int mid = low + (high - low) / 2;
if (key >= a[mid]) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}
// Returns number of pairs with absolute difference less than or equal to mid.
private int countPairs(int[] a, int mid) {
int n = a.length, res = 0;
for (int i = 0; i < n; i++) {
res += upperBound(a, i, n - 1, a[i] + mid) - i - 1;
}
return res;
}
public int smallestDistancePair(int a[], int k) {
int n = a.length;
Arrays.sort(a);
// Minimum absolute difference
int low = a[1] - a[0];
for (int i = 1; i < n - 1; i++)
low = Math.min(low, a[i + 1] - a[i]);
// Maximum absolute difference
int high = a[n - 1] - a[0];
// Do binary search for k-th absolute difference
while (low < high) {
countPairs(a, mid)
if (countPairs(a, mid) < k)
low = mid + 1;
else
high = mid;
}
return low;
}
}