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.


  • 0
    A

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


Log in to reply
 

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