# 719. Find K-th Smallest Pair Distance
#### Difficulty: Hard
link: https://leetcode.com/problems/find-k-th-smallest-pair-distance/

### 1. Binary Search
#### $O(n\ log\ (max(nums) - min(nums)) + n\ log\ n)$ runtime, $O(1)$ space

找第k個距離的問題，暴力的做法是找出所有pairs之間的距離，排序後找出第k個。然而，找所有pairs距離的時間複雜度是$O(n^2)$，排序的時間複雜度是$O(n^2\ log\ n^2)$，太慢了。

問題可以被轉變成，每次都猜一個距離，檢查這個距離是不是排在第k個之後，利用binary search找出滿足這個條件的最小值，便是答案。

套用binary search模板，距離的上下限是0到$max(nums) - min(nums)$。

關鍵在，怎麼設計feasible這個函數。

首先，利用絕對值的特性，將nums排序好，如此一來距離近的元素就會被放在一起。

為避免重複計算到pairs的距離，我們用一個for迴圈，作為pair的右邊(index是 $r$)，同時往左邊看，與num距離istance的數字(index是 $l$)，這之間pairs的距離都小於distance，用total來累加計算pairs數。

由於nums是排序好的，利用sliding window的作法，每次 $l$ 不用從開始檢查，從上次 $l$ 的位置開始往右就好，如此一來feasible函數的複雜度僅是$O(n)$。

時間複雜度為Binary search的$O(n\ log\ (max(nums) - min(nums))$和排序的$O(n\ log\ n)$的總和。

##### python

class Solution:
    def smallestDistancePair(self, nums: List[int], k: int) -> int:
        nums.sort()
        
        def feasible(distance):
            l, total = 0, 0
            for r, num in enumerate(nums):
                while nums[l] < num - distance:
                    l += 1
                total += r - l
                # early stop
                if total >= k:
                    return True
            return False
        
        left, right = 0, max(nums) - min(nums)
        
        while left < right:
            mid = left + (right - left) // 2
            if feasible(mid):
                right = mid
            else:
                left = mid + 1
        
        return left

###### tags: `leetcode`