Solution Explanation for Find K-th Smallest Pair Distance

This problem asks to find the k-th smallest distance among all pairs of numbers in a given integer array. The brute-force approach of calculating all pair distances and sorting them is inefficient, especially for large input arrays. The optimal solution uses binary search and a counting function.

Approach:

1. Sort the array: First, sort the input array nums. This is crucial for efficient counting of pairs within a given distance.

2. Binary Search: The core idea is to use binary search on the range of possible distances. The minimum possible distance is 0 (when two identical numbers are paired), and the maximum possible distance is the difference between the largest and smallest numbers in the array.

3. Counting Function (count): This function determines how many pairs have a distance less than or equal to a given dist. It iterates through the sorted array. For each number nums[i], it uses binary search (or a similar efficient approach) to find the index j such that nums[j] >= nums[i] - dist. The number of pairs with distance <= dist involving nums[i] is then i - j. Summing this for all i gives the total count of pairs with distance <= dist.

4. Binary Search Iteration: The binary search iteratively narrows down the range of possible distances. If the count(mid) (where mid is the middle distance) is greater than or equal to k, it means the k-th smallest distance is less than or equal to mid, so we search in the lower half. Otherwise, we search in the upper half.

5. Return Value: The final value of left (after the binary search converges) represents the k-th smallest pair distance.

Time Complexity Analysis:

• Sorting: O(n log n), where n is the length of nums.
• Binary Search: O(log(max_dist - min_dist)), where max_dist and min_dist are the maximum and minimum distances. In the worst case, max_dist - min_dist is O(n), so binary search is approximately O(log n).
• Counting Function: The counting function uses binary search within the loop, so its time complexity is O(n log n).

Therefore, the overall time complexity is dominated by sorting and the counting function, resulting in O(n log n).

Space Complexity:

The space complexity is dominated by the sorted array (in-place sorting can be used to reduce this, but it’s generally O(n) for auxiliary space), making it O(n).

Code Examples (with detailed comments):

Python:

import bisect
 
class Solution:
    def smallestDistancePair(self, nums: List[int], k: int) -> int:
        nums.sort()  # Sort the array
 
        def count(dist):  # Counting function
            cnt = 0
            for i, b in enumerate(nums):
                # Binary search to find j such that nums[j] >= b - dist
                j = bisect_left(nums, b - dist, 0, i) 
                cnt += i - j  # Count pairs with distance <= dist
            return cnt
 
        left, right = 0, nums[-1] - nums[0]  # Initialize search range
        while left < right:  # Binary search
            mid = (left + right) // 2
            if count(mid) >= k:
                right = mid
            else:
                left = mid + 1
        return left

Java:

import java.util.Arrays;
 
class Solution {
    public int smallestDistancePair(int[] nums, int k) {
        Arrays.sort(nums); //Sort the array
 
        int left = 0, right = nums[nums.length - 1] - nums[0]; //Initialize search range
        while (left < right) { //Binary search
            int mid = (left + right) / 2;
            if (count(nums, mid) >= k) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
 
    private int count(int[] nums, int dist) { //Counting function
        int count = 0;
        for (int i = 0; i < nums.length; ++i) {
            int j = 0;
            // Find j such that nums[j] >= nums[i] - dist using binary search (efficient way)
            int left = 0, right = i;
            while (left < right) {
                int mid = (left + right) / 2;
                if (nums[mid] >= nums[i] - dist) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            count += i - left; //Count pairs
        }
        return count;
    }
}

The other languages (C++, Go, TypeScript, JavaScript) follow a similar structure, with appropriate adaptations for language-specific features (like lower_bound in C++ or bisect_left in Python). The core algorithmic approach remains the same.