Sponsored
Sponsored
This approach utilizes sorting and a min-heap (or priority queue) to efficiently manage and retrieve the k-th smallest distance. The key steps are:
nums. This simplifies the process of finding the distances as all distance calculations will involve consecutive elements.Time Complexity: O(n^2 log n) due to the double loop and heap operations.
Space Complexity: O(n^2) for storing all possible distances in the heap.
1import heapq
2
3def find_kth_smallest_pair_distance(nums, k):
4 nums.sort()
5 pq = []
6 for i in range(len(nums)-1):
7 for j in range(i+1, len(nums)):
8 heapq.heappush(pq, abs(nums[j] - nums[i]))
9
10 for _ in range(k-1):
11 heapq.heappop(pq)
12 return heapq.heappop(pq)First, the array is sorted to enable orderly distance calculations. A min-heap (priority queue) is used to efficiently manage the distances and extract the k-th smallest. After computing and storing distances in the heap, we extract the smallest k elements, finally returning the k-th one.
This more efficient approach combines binary search with a two-pointer technique. The principal idea is to use binary search over distance values to pinpoint the k-th smallest distance. It involves:
nums.Time Complexity: O(n log n + n log(maxDistance))
Space Complexity: O(1) as no additional space beyond fixed variables is used.
1#include <vector>
2#include <algorithm>
int countPairs(std::vector<int>& nums, int max_dist) {
int count = 0, j = 0;
for (int i = 0; i < nums.size(); i++) {
while (j < nums.size() && nums[j] - nums[i] <= max_dist) j++;
count += j - i - 1;
}
return count;
}
int findKthSmallestPairDistance(std::vector<int>& nums, int k) {
std::sort(nums.begin(), nums.end());
int left = 0, right = nums.back() - nums.front();
while (left < right) {
int mid = (left + right) / 2;
if (countPairs(nums, mid) < k) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}The primary focus here is on sorting to enable efficient searching over possible distances via binary search to find the smallest k-th distance. The inner helper efficiently counts pairs with a maximum distance of max_dist using two pointers.