LeetCode - Find K-th Smallest Pair Distance
https://leetcode.com/problems/find-k-th-smallest-pair-distance/
Problem
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.
Solution
There is a brute forced solution which is generate all pair-distance and maintain a heap with O(k) elements, which i think will TLE. The time complexity is O(n^2 * logK) which can be converted into O(n^2 log(n^2)).
My first solution is: try to find the smallest distance that has more than or equal k smaller pair-distance.
1 | for distance := range(0, 1000000) { //minDistance -> maxDistance |
There are 3 things we need to consider here:
- Why smallest distance is the correct answer?
- How can we optimize the distance for loop?
- What is the best way to implement
countSmallerOrEqualPairDistance?
Answers:
“Why smallest distance is the correct answer?”. We have to do some math here:
- Assumed we have the sorted array
diffwhich is all pair distance:diff[0] <= diff[1] <= ... <= diff[k] <= diff[k+1] <= .. <= diff[N*(N-1)/2]where (N is length of input array) - The
distanceis going from 0 -> maxDistance, the firstdistancesatisfiescnt := countSmallerOrEqualPairDistance(distance) >= kwill be in in the range[diff[k], diff[k+1])since ifcnt < diff[k]then there are less than k pair distances smaller thancnt. The same as, ifcnt >= diff[k+1]there will be more than k pair distance smaller thancnt. - => The smallest distance is the result.
- Assumed we have the sorted array
“How can we optimize the distance for loop?”. As proof in the first question 1, there is a linear attribute when finding
distance. We can use binary search to find the smallestdistance.“What is the best way to implement
countSmallerOrEqualPairDistance(distance)?”. We can first sort the input arraynums. For each positioniinnums, we find the farest positionjon the right which isnums[j] - nums[i] <= distance. There are three solutions:- We can do the O(N^2) count here. Which caused the final time complexity O(N^2Log(MaxDiff)). It’s slightly better than the brute forced solution since MaxDiff < N^2.
- For each position
i, using binary search to find the farestj. This solution has O(NlogN) time complexity, the final time complexity is O(NlogNlogMaxDiff) which enough to get accepted. - The best solution here is that using two pointers:
- We can maintain the farest
jfor the currenti. - We can easily see that, if i += 1, j will stay the same or move to the right.
- => For each position, we only traverse thought 2 times.
- => Time complexity is O(N) which leads to final time complexity is O(N*logMaxDiff)
- We can maintain the farest
Code for binary search solution:
1 | func smallestDistancePair(nums []int, k int) int { |
Code for two pointer solution:
1 | func smallestDistancePair(nums []int, k int) int { |
Support me via: https://ko-fi.com/iamquang95