Find Kth 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 becauseguess >= 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 justsum(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
.

@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).

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