aboutsummaryrefslogtreecommitdiff
path: root/find_k_small_pair_dist.py
diff options
context:
space:
mode:
Diffstat (limited to 'find_k_small_pair_dist.py')
-rw-r--r--find_k_small_pair_dist.py44
1 files changed, 44 insertions, 0 deletions
diff --git a/find_k_small_pair_dist.py b/find_k_small_pair_dist.py
new file mode 100644
index 0000000..b49157d
--- /dev/null
+++ b/find_k_small_pair_dist.py
@@ -0,0 +1,44 @@
+# 719. Find K-th Smallest Pair Distance
+
+"""
+the distance of a pair of integers 'a' and 'b' is defined as the absolute
+different between 'a' and 'b'. given an integer array 'nums' and an integer
+'k', return the smallest k'th distance among all the pairs 'nums[i]' and
+'nums[j]' where '0 <= i < j < nums.len'.
+"""
+
+
+class Solution(object):
+ def smallestDistancePair(self, nums, k):
+ """
+ :type nums: List[int]
+ :type k: int
+ :rtype: int
+ """
+
+ def enough(dist):
+ cnt, i, j = 0, 0, 0
+ while i < n or j < n:
+ while j < n and nums[j] - nums[i] <= dist:
+ j += 1
+ cnt += j - i - 1
+ i += 1
+ return cnt >= k
+
+ nums.sort()
+ n = len(nums)
+ left, right = 0, nums[-1] - nums[0]
+ while left < right:
+ mid = left + (right - left) // 2
+ if not enough(mid):
+ left = mid + 1
+ else:
+ left = mid
+ return left
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.smallestDistancePair(nums=[1, 3, 1], k=1))
+ print(obj.smallestDistancePair(nums=[1, 1, 1], k=2))
+ print(obj.smallestDistancePair(nums=[1, 6, 1], k=3))