_719. Find K-th Smallest Pair Distance.md

719. Find K-th Smallest Pair Distance

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : August 14, 2024

Last updated : August 14, 2024

---

Related Topics : Array, Two Pointers, Binary Search, Sorting

Acceptance Rate : 45.34 %

---

I originally tried brute forcing which didn't work. Then I tried bucketsorting with the number of digits of each difference, which resulted in a TLE of 17/19 passed (the same as brute force). I think this mainly due to the log operations being slow, though it's unconfirmed.

---

Solutions

• h719 counting bucketsort.py

Python

h719 counting bucketsort.py

class Solution:
    def smallestDistancePair(self, nums: List[int], k: int) -> int:
        buckets = [0 for _ in range(max(nums) + 1)]

        for i, v in enumerate(nums[:-1]) :
            for u in nums[i + 1:] :
                buckets[abs(u - v)] += 1

        indx = 0
        while k > buckets[indx] :
            k -= buckets[indx]
            indx += 1
        return indx