Find K-th Smallest Pair Distance


  • 0

    Click here to see the full article post


  • 0
    R
    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


  • 0
    S

    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
    

    `


  • 0
    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.


  • 0
    I

    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,


  • 0
    T

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


  • 0
    J

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


  • 0
    K

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


  • 0

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


Log in to reply
 

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