How do you solve Find K-th Smallest Pair Distance on LeetCode?

Find K-th Smallest Pair Distance (LeetCode #719) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n log(max_distance)) time complexity and O(1) space complexity. Key insight: Sorting the array helps in efficiently calculating distances and using binary search.

What is the brute force solution for Find K-th Smallest Pair Distance?

The brute force approach for Find K-th Smallest Pair Distance is Brute Force, with O(n²) time complexity and O(n²) space complexity. The brute force approach involves calculating the distance for every possible pair of integers in the array. This is straightforward but inefficient for larger arrays as it examines all combinations. The optimal Optimal Solution approach improves this to O(n log(max_distance)).

What algorithm or data structure is used to solve Find K-th Smallest Pair Distance?

Find K-th Smallest Pair Distance uses the following concepts: Array, Two Pointers, Binary Search, Sorting. The recommended patterns to study are: Binary Search, Two Pointers.

What are the interview tips for Find K-th Smallest Pair Distance?

Always consider edge cases, such as arrays with duplicate values. Explain your thought process clearly while coding; it helps the interviewer follow your logic. Practice binary search problems, as they often appear in interviews.

What are common mistakes when solving Find K-th Smallest Pair Distance?

Not sorting the array before performing distance calculations. Confusing the indices when counting pairs, leading to incorrect counts.

#719

Find K-th Smallest Pair Distance

Hard

ArrayTwo PointersBinary SearchSortingBinary SearchTwo Pointers

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n log(max_distance))
Space	O(n²)	O(1)

💡

Intuition

Time O(n log(max_distance))Space O(1)

The optimal solution uses binary search on the possible distance values and counts how many pairs have a distance less than or equal to a mid value. This allows us to efficiently hone in on the k-th smallest distance without generating all pairs.

⚙️

Algorithm

6 steps

1Step 1: Sort the input array to facilitate distance calculations.
2Step 2: Set low to 0 and high to the difference between the maximum and minimum values in the sorted array.
3Step 3: Perform binary search: while low <= high, calculate mid as (low + high) / 2.
4Step 4: Count how many pairs have a distance <= mid using a two-pointer technique.
5Step 5: If the count is less than k, move low to mid + 1; otherwise, move high to mid - 1.
6Step 6: The low variable will represent the k-th smallest distance when the search completes.

solution.py22 lines

1# Full working Python code
2
3def countPairs(nums, mid):
4    count = 0
5    left = 0
6    for right in range(len(nums)):
7        while nums[right] - nums[left] > mid:
8            left += 1
9        count += right - left
10    return count
11
12
13def kthSmallestDistance(nums, k):
14    nums.sort()
15    low, high = 0, nums[-1] - nums[0]
16    while low < high:
17        mid = (low + high) // 2
18        if countPairs(nums, mid) < k:
19            low = mid + 1
20        else:
21            high = mid
22    return low

ℹ

Complexity note: The time complexity arises from the binary search over the distance range (which is log(max_distance)) and counting pairs (which is O(n)). The space complexity is O(1) since we are not using any additional data structures that grow with input size.

1Sorting the array helps in efficiently calculating distances and using binary search.
2The two-pointer technique allows counting pairs in linear time.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.