leetcode - 719. Find K-th Smallest Pair Distance

Description

The distance of a pair of integers a and b is defined as the absolute difference between a and b.

Given an integer array nums and an integer k, return the kth smallest distance among all the pairs nums[i] and nums[j] where 0 <= i < j < nums.length.

Example 1:

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.

Example 2:

Input: nums = [1,1,1], k = 2 Output: 0

Example 3:

Input: nums = [1,6,1], k = 3 Output: 5

Constraints:

n == nums.length 2 <= n <= 10^4 0 <= nums[i] <= 10^6 1 <= k <= n * (n - 1) / 2 Solution Brute Force

Iterate all the possible pairs, then find the shortest distance. Use a max-root heap of size k to keep all the distance we have calculated.

Time complexity: o ( n 2 ) o(n^2) o(n2)
Space complexity: o ( k ) o(k) o(k)

Binary Search

The search range is [0, max(nums) - min(nums)], the difficult part is to find the monotonic part.

For binary search, we need to find a condition that, if condition(k) is True then condition(k + 1) is True.

Consider we have a given distance, there would be a point that, all the distance that is larger than the given distance have more k pairs, and all the distance that is smaller than given distance have less than k pairs.

[d1, d2, d3, d4, d5, d6...] ^

If d5 is our target distance, then d6 and larger distances would have more than k pairs.

So we need a function, with the distance as input, and the output is bool, where it’s True if input distance has k or more pairs, and False otherwise.

For this function, we could use 2 pointers. Image we have a fixed index i, and we have j where nums[j] - nums[i] <= distance, we keep moving j to right until nums[j] - nums[i] > distance, then we get j - i - 1 pairs.
Then we move i forward for 1 step, and check if nums[j] - nums[i] <= distance, if so, we keep moving j until it’s not.
Keep this process until i reaches the end of the list.

Time complexity: o ( n log ⁡ n ) o(n\log n) o(nlogn), o ( n log ⁡ n ) o(n\log n) o(nlogn) for sorting and binary search, o ( n ) o(n) o(n) for 2 pointers.
Space complexity: o ( 1 ) o(1) o(1)

Code Brute Force class Solution: def smallestDistancePair(self, nums: List[int], k: int) -> int: k_small_distance = [] for i in range(len(nums)): for j in range(i + 1, len(nums)): distance = abs(nums[i] - nums[j]) heapq.heappush(k_small_distance, -distance) if len(k_small_distance) > k: heapq.heappop(k_small_distance) return -min(k_small_distance) Binary Search class Solution: def smallestDistancePair(self, nums: List[int], k: int) -> int: def is_enough(distance: int) -> bool:"""Returns: True: if there are k or more pairs with the distance or less False: if there are less than k pairs with the distance or less"""count = 0 i, j = 0, 0 while i < len(nums) or j < len(nums): while j < len(nums) and nums[j] - nums[i] <= distance: j += 1 count += (j - i - 1) i += 1 return count >= k nums.sort() left, right = 0, nums[-1] - nums[0] while left < right: mid = (left + right) >> 1 if is_enough(mid): right = mid else: left = mid + 1 return (left + right) >>1