719. Find K-th Smallest Pair Distance

[mah-shamim]

Topics: Array, Two Pointers, Binary Search, Sorting

The distance of a pair of integers a and b is defined as the absolute difference between a and b.

Given an integer array nums and an integer k, return the kth smallest distance among all the pairs nums[i] and nums[j] where 0 <= i < j < nums.length.

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 1^st 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

Constraints:

• n == nums.length
• 2 <= n <= 104
• 0 <= nums[i] <= 106
• 1 <= k <= n * (n - 1) / 2

Hint:

1. Binary search for the answer. How can you check how many pairs have distance <= X?

[mah-shamim]

We can use a combination of binary search and two-pointer technique. Here's a step-by-step approach to solving this problem:

Approach:

1. Sort the Array: First, sort the array nums. Sorting helps in efficiently calculating the number of pairs with a distance less than or equal to a given value.

2. Binary Search on Distance: Use binary search to find the k-th smallest distance. The search space for the distances ranges from 0 (the smallest possible distance) to max(nums) - min(nums) (the largest possible distance).

3. Count Pairs with Distance ≤ Mid: For each mid value in the binary search, count the number of pairs with a distance less than or equal to mid. This can be done efficiently using a two-pointer approach.

4. Adjust Binary Search Range: Depending on the number of pairs with distance less than or equal to mid, adjust the binary search range. If the count is less than k, increase the lower bound; otherwise, decrease the upper bound.

Let's implement this solution in PHP: 719. Find K-th Smallest Pair Distance

<?php
function countPairsWithDistanceLessThanOrEqualTo($nums, $mid) {
    $count = 0;
    $left = 0;

    for ($right = 1; $right < count($nums); $right++) {
        while ($nums[$right] - $nums[$left] > $mid) {
            $left++;
        }
        $count += $right - $left;
    }

    return $count;
}

function smallestDistancePair($nums, $k) {
    sort($nums);
    $low = 0;
    $high = $nums[count($nums) - 1] - $nums[0];

    while ($low < $high) {
        $mid = intval(($low + $high) / 2);

        if (countPairsWithDistanceLessThanOrEqualTo($nums, $mid) < $k) {
            $low = $mid + 1;
        } else {
            $high = $mid;
        }
    }

    return $low;
}

// Example usage:
$nums = [1, 3, 1];
$k = 1;
echo smallestDistancePair($nums, $k);  // Output: 0

?>

Explanation:

• countPairsWithDistanceLessThanOrEqualTo: This function counts how many pairs have a distance less than or equal to mid. It uses two pointers, where right is the current element, and left is adjusted until the difference between nums[right] and nums[left] is less than or equal to mid.

• smallestDistancePair: This function uses binary search to find the k-th smallest distance. The low and high values define the current search range for the distances. The mid value is checked using the countPairsWithDistanceLessThanOrEqualTo function. Depending on the result, the search space is adjusted.

This algorithm efficiently finds the k-th smallest pair distance with a time complexity of O(n log(max(nums) - min(nums)) + n log n).

[basharul-siddike]

Thanks for solving the problem of "Find K-th Smallest Pair Distance"

[mah-shamim]

Thanks