Documentation Index
Fetch the complete documentation index at: /llms.txt
Use this file to discover all available pages before exploring further.
Tested Python solution for LeetCode 719 with 14 pytest cases. Generate a practice environment with lcpy.
lcpy gen -n 719 # by problem number
lcpy gen -s find_k_th_smallest_pair_distance # by problem name
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.
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.
Input: nums = [1,1,1], k = 2
Output: 0
Input: nums = [1,6,1], k = 3
Output: 5
from bisect import bisect_right
class Solution:
# Time: O(n log n + n log W) where W = max(nums) - min(nums)
# Space: O(n)
def smallest_distance_pair(self, nums: list[int], k: int) -> int:
nums = sorted(nums)
n = len(nums)
def count_pairs_within(dist: int) -> int:
count = 0
for i in range(n):
count += bisect_right(nums, nums[i] + dist, lo=i + 1) - (i + 1)
return count
low, high = 0, nums[-1] - nums[0]
while low < high:
mid = (low + high) // 2
if count_pairs_within(mid) >= k:
high = mid
else:
low = mid + 1
return low
| Time | Space |
|---|---|
| O(n log n + n log W) where W = max(nums) - min(nums) | O(n) |