[LeetCode] Challenge log 719

Posted on |
719. Find K-th Smallest Pair Distance

Related problem: #378, # 668. The difference is how to count how many smaller. To count quickly, you need to:

  1. Sort the array first.
  2. Do a while loop within a for loop; Each time the element that just gives enough distance to the one that in the outer loop; For next iteration, start looking from the last element found to save time.

Given an integer array, return the k-th smallest distance among all the pairs. The distance of a pair (A, B) is defined as the absolute difference between A and B.

Example 1:

1
2
3
4
5
6
7
8
9
10
Input:
nums = [1,3,1]
k = 1
Output: 0 
Explanation:
Here are all the pairs:
(1,3) -> 2
(1,1) -> 0
(3,1) -> 2
Then the 1st smallest distance pair is (1,1), and its distance is 0.

Note:

  1. 2 <= len(nums) <= 10000.
  2. 0 <= nums[i] < 1000000.
  3. 1 <= k <= len(nums) * (len(nums) - 1) / 2.
Soulution:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution:
    def smallestDistancePair(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        nums = sorted(nums)
        n = len(nums)
        
        ### Important part
        def countLower(mid):
            count = 0
            lb = 0
            for i in range(n): 
                while nums[i] - nums[lb] > mid:
                    lb += 1
                count += (i - lb)
            return count
        ### ----------------
        
        low = 0
        high = nums[-1] - nums[0]
        while low < high:
            mid = (low + high) // 2
            if countLower(mid) < k:
                low = mid + 1
            else:
                high = mid
        return low
0%