Find K-th Smallest Pair Distance

class Solution {
public:
    int minDistancePair(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int len = nums.size();

        // Binary search bounds
        int start = 0;
        int end = nums[len - 1] - nums[0];

        while (start < end) {
            int mid = (start + end) / 2;

            // Get count of pairs with max distance equal to mid
            int pairCount = getPairCount(nums, mid);

            // Determine the new bounds
            if (pairCount < k) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }
        return start;
    }

private:
    // Helper function to count pairs
    int getPairCount(vector<int>& nums, int maxDist) {
        int pairNum = 0;
        int len = nums.size();
        int j = 0;

        for (int i = 0; i < len; ++i) {
            while (nums[i] - nums[j] > maxDist) {
                ++j;
            }
            pairNum += i - j;
        }
        return pairNum;
    }
};

This problem involves finding the K-th smallest pair distance in an array of integers using C++. The approach utilizes a combination of sorting, binary search, and a count mechanism for efficient computation:

• First, sort the array to facilitate the calculation of differences between elements.
• Define the binary search bounds based on the range of the differences (i.e., between 0 and the difference between the largest and smallest array elements).
• Perform binary search:
  • For each middle value mid, calculate the number of pairs whose distance is less than or equal to mid using a helper function getPairCount.
  • Adjust the binary search bounds based on whether the count of pairs is less than or equal to or greater than K; this helps to zero in on the K-th smallest distance.

The helper function getPairCount:

• Counts pairs that comply with the distance condition by leveraging the sorted nature of the array.
• Efficiently counts by maintaining two pointers, adjusting their positions based on whether the current pair distance exceeds the specified maximum distance (maxDist) or not.

By utilizing sorting and binary search, this solution ensures efficient handling of even large datasets by keeping operations within logarithmic complexity concerning the array size.

class Solution {

    public int minimumDistancePair(int[] nums, int k) {
        Arrays.sort(nums);
        int len = nums.length;

        // Set initial binary search bounds
        int start = 0;
        int end = nums[len - 1] - nums[0];

        while (start < end) {
            int middle = (start + end) / 2;

            // Calculate the number of pairs with max allowable distance
            int pairCount = getPairsCount(nums, middle);

            // Update search bounds based on pair count
            if (pairCount < k) {
                start = middle + 1;
            } else {
                end = middle;
            }
        }
        return start;
    }

    // Helper method to count pairs within a specified maximum distance
    private int getPairsCount(int[] nums, int maxDist) {
        int pairCounter = 0;
        int len = nums.length;
        int front = 0;

        for (int back = 0; back < len; ++back) {
            // Move the front pointer to keep pairs within the maxDist
            while (nums[back] - nums[front] > maxDist) {
                ++front;
            }
            // Increment the count for each valid pair formed
            pairCounter += back - front;
        }
        return pairCounter;
    }
}

This Java solution addresses the problem of finding the K-th smallest pair distance in an array of integers. Here is a breakdown of how the solution operates:

• Sorting the Array: Begin by sorting the integers in the array. This preliminary step simplifies the process of calculating distances between pairs.

• Binary Search Setup: Implement binary search to efficiently find the K-th smallest distance. Set the initial search bounds start as 0 and end to the difference between the maximum and minimum values in the array.

• Binary Search Execution: During each iteration of the binary search:

  • Calculate the middle point of the current bounds.
  • Use the getPairsCount method to count the number of valid pairs that have a distance less than or equal to the middle value.
  • Adjust the search bounds based on the count of valid pairs relative to K. If the number of pairs is less than K, reduce the search range to higher distances by setting start to middle + 1. If the number is greater or equal, focus on smaller distances by setting end to middle.

• Counting Pairs Method: getPairsCount calculates how many pairs have a distance less than or equal to a given maxDist. It utilizes two pointers, back and front, moving front to ensure that the distance condition is maintained, and incrementing the count of valid pairs accordingly.

• Final Result: Once the while loop exits, start will hold the value of the K-th smallest pair distance, which is then returned.

This approach ensures efficiency by leveraging binary search, cutting down the possibilities with each iteration based on dynamically calculated conditions, thus achieving an optimal solution to the problem.

class Solution:
    def findSmallestDistPair(self, values: List[int], index: int) -> int:
        values.sort()
        length = len(values)

        # Set initial search boundaries
        low = 0
        high = values[-1] - values[0]

        while low < high:
            mid = (low + high) // 2

            # Compute the number of pairs not exceeding mid distance
            count = self._pairs_within_limit(values, mid)

            # Binary search adjustment
            if count < index:
                low = mid + 1
            else:
                high = mid

        return low

    # Helper to count pairs where the maximum allowed distance is max_dist
    def _pairs_within_limit(self, values: List[int], max_dist: int) -> int:
        total_pairs = 0
        length = len(values)
        start = 0

        for end in range(length):
            # Maintain distance constraint
            while values[end] - values[start] > max_dist:
                start += 1
            # Calculate possible pairs
            total_pairs += end - start
        return total_pairs

This Python solution provides a method to find the k-th smallest pair distance among a list of integers. The main method, findSmallestDistPair, utilizes a binary search algorithm to efficiently determine this distance. Here's how the solution works:

• First, the list of integers, values, is sorted. Sorting is essential as it eases the computation of differences among pairs.
• The search for the k-th smallest distance runs between the smallest and the largest potential distance in the sorted list. The variables low and high are initialized to the smallest distance (0) and the maximum distance (values[-1] - values[0]), respectively.
• The binary search repeatedly narrows down the search range. For each midpoint mid in the current range:
  • The method _pairs_within_limit counts how many pairs have a distance less or equal to mid.
  • Depending on the count relative to index, the search boundaries (low and high) are adjusted. If the count of valid distances is less than index, the search continues in the upper range; otherwise, it focuses on the lower range.
• The search ends when low equals high, which will be the k-th smallest distance.

The helper method _pairs_within_limit assists in this process by:

• Iterating through the list and for each element end in values:
  • Adjusting the start index such that the distance to end does not exceed max_dist.
  • Counting how many pairs meet this condition by subtracting start from end.

This approach effectively uses binary search combined with efficient counting of valid pairs to provide a solution that is faster than a simple brute-force technique. This efficiency is crucial for larger datasets.