We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find K-th Smallest Pair Distance

Number: 719

Difficulty: Hard

Paid? No

Companies: Amazon, Bloomberg, Pinterest, Flipkart, Google

Problem Description

Given an integer array and an integer k, find the kth smallest distance among all pairs (nums[i], nums[j]) with i < j. The distance of a pair is defined as the absolute difference between the two numbers.

Key Insights

  • Sorting the array simplifies the calculation since the absolute difference is monotonic when traversing sequentially.
  • Instead of generating all pair distances, use binary search on the range of possible distances.
  • A two-pointer technique can efficiently count the number of pairs with a distance less than or equal to a given middle value.
  • The binary search converges on the kth smallest distance based on the count of valid pairs.

Space and Time Complexity

Time Complexity: O(n log(max - min) + n log n) where n is the number of elements. O(n log n) for sorting and O(n log(max - min)) for binary search across the distance range. Space Complexity: O(1) extra space (ignoring the space required for sorting).

Solution

The approach starts by sorting the input array to leverage the ordered property of the numbers. The possible pair distances range between 0 and (max(nums) - min(nums)). Use binary search over this range to find the smallest distance d such that there are at least k pairs with a distance less than or equal to d. A helper function uses a two-pointer method on the sorted array to count the number of pairs satisfying the condition. Adjust the binary search boundaries based on this count until convergence.

Code Solutions

# Function to find the kth smallest pair distance using binary search and two pointers
def smallestDistancePair(nums, k):
    # Sort the array to simplify finding pair distances.
    nums.sort()

    # Define the search range for possible distances
    low, high = 0, nums[-1] - nums[0]
    
    # Helper function: count number of pairs with difference <= mid.
    def count_pairs(mid):
        count, left = 0, 0
        # Use two pointers to count valid pairs.
        for right in range(len(nums)):
            while nums[right] - nums[left] > mid:
                left += 1
            count += right - left
        return count

    # Binary search over the possible distances.
    while low < high:
        mid = (low + high) // 2  # Midpoint of current distance range.
        if count_pairs(mid) < k:
            low = mid + 1  # Not enough pairs, increase low bound.
        else:
            high = mid  # Enough pairs, try a smaller distance.
    return low

# Example usage:
print(smallestDistancePair([1, 3, 1], 1))  # Expected Output: 0
← Back to All Questions