LeetCode 719: Find K-th Smallest Pair Distance Solution

Master LeetCode problem 719 (Find K-th Smallest Pair Distance), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

719. Find K-th Smallest Pair Distance

Hard

Array Two Pointers Binary Search Sorting

Problem Explanation

Explanation

To solve this problem, we need to find the kth smallest distance among all pairs of integers in the given array nums. We can approach this by using binary search on the possible range of distances. We start by sorting the array nums and then binary search on the possible range of distances to find the kth smallest distance. For each mid value in the binary search, we use a sliding window approach to count the number of pairs with distance less than or equal to mid. If the count is less than k, we update our binary search range accordingly.

Algorithm:

Sort the input array nums.
Perform binary search on the range of distances possible.
For each mid value, use a sliding window approach to count the number of pairs with distance less than or equal to mid.
If the count is less than k, update the binary search range.
Repeat until we find the kth smallest distance.

Time Complexity: O(n log n + n log W), where n is the length of the input array nums and W is the maximum possible distance.

Space Complexity: O(1)

Solution Code

class Solution {
    public int smallestDistancePair(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length;
        int low = 0, high = nums[n - 1] - nums[0];
        
        while (low < high) {
            int mid = low + (high - low) / 2;
            int count = 0, left = 0;
            
            for (int right = 0; right < n; right++) {
                while (nums[right] - nums[left] > mid) {
                    left++;
                }
                count += right - left;
            }
            
            if (count < k) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        
        return low;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 719 (Find K-th Smallest Pair Distance)?

This page provides optimized solutions for LeetCode problem 719 (Find K-th Smallest Pair Distance) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 719 (Find K-th Smallest Pair Distance)?

The time complexity for LeetCode 719 (Find K-th Smallest Pair Distance) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 719 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 719 in Java, C++, or Python.

Back to LeetCode Solutions