#719

Find K-th Smallest Pair Distance

candidate master · 1520 · lc hard +32 · verified · 46.4% accepted · 3,916 likes · top 31%

Description

The distance between two integers a and b is |a - b|. Given an integer array nums and an integer k, consider all pairs (nums[i], nums[j]) with 0 <= i < j < nums.length and return the k^th smallest pairwise distance.

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

Code

1

2

3

class Solution:
    def smallestDistancePair(self, nums: List[int], k: int) -> int:

class Solution:
    def smallestDistancePair(self, nums: List[int], k: int) -> int: