# Find K-th Smallest Pair Distance

• ``````Now, for every point i, the number of points j with i < j and nums[j] - nums[i] <= guess is prefix[x+guess] - prefix[x] + (count[i] - multiplicity[i]), where count[i] is the number of ocurrences of nums[i] in nums.
``````

I don't get the intuition behind this. Can someone explain please? Thanks

• There is a small change in the Approach #1: Heap [Time Limit Exceeded]
`
from heapq import heapify, heappush, heappop
class Solution(object):
"""docstring for Solution."""
def init(self):
super(Solution, self).init()

``````def KthsmallestpairDist(self, nums, k):
#sort the points
nums.sort() #[1,1,3] , heap = [(0,0,1),(2,1,2)]
heap = [(nums[i+1]-nums[i], i, i+1)
for i in xrange(len(nums)-1)]
heapify(heap) #Makes it into a BST
print(heap)

for _ in xrange(k):
d, root, nei = heappop(heap)
if nei+1<len(nums):
heappush(heap, (nums[nei + 1] - nums[root], root, nei + 1))
return d
``````

`

• @richard.zhang.969 I'll give my understanding.

First there is no array `count`. `multiplicity` is a count of the number of 0 distance pairs at each index. You could just sum this array to get the total number of 0 distance pairs. Then because `guess >= 0`, this total always counts towards the number of distance pairs `<= guess`.

Now we use `prefix` to calculate the remaining distance pairs - those that are `>0 and <= guess`. To do that is just `sum(prefix[x + guess] - prefix[x] for x in nums)`.

`prefix[x + guess] - prefix[x]` is the count of values in the nums array <= x + guess - the count of values in the nums array <= x. Another way of saying that is: the count of distance pairs that have x as the smaller number in the pair and a distance `>0 and <= guess`.

• Thank you for the post, really clear and logical. I just have a small question that for the `mi` , how do you guarantee there will be a distance equals to the `mi` ?

`int mi = (lo + hi) / 2;` it's not the actual distance,

• @icesnakejin This is because the binary search always finds the smallest mi that satisfies count>=k. Imagine when we find a large mi with count >= k, hi is set to mi, and we keep looking to the left.

• For the 3rd solution "Approach #3: Binary Search + Sliding Window [Accepted]", "The logW factor comes from our binary search, and we do O(N) work inside our call to possible (or to calculate count in Java)." I think the complexity for the work inside the call is O(N^2) instead of O(N), since there are two loops. You can optimize it to O(N log N), so the best time complexity for this solution is ( N log N log W + N log N).

• The python code for approach 3 fails the tests. You have to return int(lo).

• @keenencates I'm using python 2. In python 3, use `mi = (lo + hi) // 2` to do integer division instead of float division.

• don't think you explained section two properly, but yeah nice solution. it makes sense now

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.