719. Find K-th Smallest Pair Distance

HardArrayTwo PointersBinary SearchSorting

Problem Description

The goal of this problem is to find the kth smallest distance between any two distinct elements within an array nums. The distance between a pair (nums[i], nums[j]) is defined as the absolute difference between their values, subject to the condition that i is less than j. In other words, we're looking at all possible pairs where each element comes before the other in the array to avoid repetitions (since order doesn't matter in finding the absolute difference).

Intuition

To solve this problem, we make use of a two-part approach: sorting and binary search.

Sorting: We start by sorting the array nums. This step is crucial because it gives us a way to efficiently count pairs with a specific distance using a linear pass through the array. If nums is sorted, any pair of numbers (a, b) such that b >= a+d (where d is our target distance) contributes to the count of distances that are at least d.
Binary Search: Next, we perform a binary search, not on the original array, but on the range of possible distances (0 to the maximum difference between any two elements in nums). The key insight here is that if we can count how many pairs have a distance smaller than or equal to a given value, we can decide whether to move higher or lower in the range of possible distances to find our kth smallest distance.
Count Function: Within the binary search, we utilize a custom count function to count how many pairs have a distance less than or equal to the current distance being considered in the binary search. This count function takes advantage of the sorted nature of nums. For any number b in nums, we find a such that a = b - current_distance and count all numbers between a and b to get the number of pairs whose distance is at most the current distance we are checking. We use the bisect_left function to find the first index where a could be inserted to maintain the sorted order.
Binary Search Application: The bisect_left function is then used again, this time with our range of potential distances and passing our count function as the key. This allows us to find the smallest distance such that the number of pair distances less than or equal to it is at least k.

By combining sorting and binary search, the solution effectively narrows down the exact distance that is the kth smallest among all pairs, ensuring an efficient yet simple method to solve the problem.

Learn more about Two Pointers, Binary Search and Sorting patterns.

Solution Approach

The solution approach largely relies on binary search and the bisect_left library function from Python's bisect module. Here's how we use these components along with some sorting:

Sorting the Array: We begin by sorting the input array nums. Sorting is essential because it allows us to exploit the property where for any sorted sequence, the difference between any two elements is non-decreasing as you go from left to right.
Binary Search on Distances: We perform a binary search on the range of possible distances which are from 0 to nums[-1] - nums[0] (the largest possible distance in the sorted array). Note that instead of the elements of the array, we're searching through potential distances, probing to find the one that will give us the kth smallest pair distance.
The Count Function: The count(dist) function is a helper function that counts how many pairs in the sorted nums array have a distance less than or equal to dist. We do this by iterating over each element b in the array and using bisect_left to find the first index where b - dist could fit (this would be the element a). The count of elements from this index to i (current index of b) gives us the number of pairs with one element less than or equal to b - dist and the other equal to b. Thereby, the difference between the indices gives us the pairs count with a maximum distance of dist.
Using Bisect to Find the Kth Distance: Finally, bisect_left is used on the range of possible distances with our count function as the key. This means that for each potential distance dist that the binary search is considering, bisect_left uses the count function to determine if the number of pairs with a distance less than or equal to dist is less than k. If the count is less than k, bisect_left discards the left part (smaller distances) and moves right (towards larger distances) to find the first distance where the number of pairs is at least k.

In essence, what we've done is utilize binary search in a somewhat unconventional manner. Instead of searching for a value in the array, we're searching for the smallest value within a range (here, a calculated range of distances) such that a condition (count of pairs with at least this distance) holds true, therefore finding the kth smallest distance pair in the array.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

To illustrate the solution approach, let's go through an example. Suppose we have the array nums = [1, 6, 11, 14], and we want to find the 3rd smallest distance between any two distinct elements.

Sorting the Array: First, we sort the array. In this case, the array is already sorted: [1, 6, 11, 14].
Binary Search on Distances: We identify the range of the possible distances. The smallest distance is 0 (for identical elements), and the largest is 14 - 1 = 13.
The Count Function: Now, we need a function to count pairs with distance less than or equal to dist. For example, if dist = 4, we would find:
- Pairs for b = 6: None, since no a exists in [1] such that 6 - a <= 4.
- Pairs for b = 11: The element that fits is 6 (11 - 6 = 5 is not less than or equal to 4), so there are 0 pairs.
- Pairs for b = 14: The element that fits is 11 (14 - 11 = 3 is less than or equal to 4), so there is 1 pair [11, 14].
Thus for dist = 4, the count is 1.
Using Bisect to Find the Kth Distance: We apply a binary search (using bisect_left) to the range [0, 13] to find the smallest distance dist such that there are at least k = 3 pairs with distance less than or equal to dist.

Now, we execute the steps of binary search to find the 3rd smallest pair distance:

First Iteration: Check mid = (0 + 13) / 2 = 6.5, rounded down to 6. Using the count function, we find there are three pairs with distances less than or equal to 6: [1, 6], [6, 11], and [11, 14]. Since we have found exactly 3 pairs, we know dist = 6 could be the 3rd smallest distance.
Second Iteration: Now to ensure that 6 is the smallest possible distance with at least 3 pairs, we need to check if any smaller number of pairs can still meet the k = 3 condition. We check left of 6, using mid = (0 + 6) / 2 = 3. The pairs with distance less than or equal to 3 are [11, 14], so just one pair, which is not enough.
Third Iteration: Since 3 is too small, we now check between 4 and 6. Let mid = (4 + 6) / 2 = 5. Now, the count function returns two pairs with distances less than or equal to 5: [1, 6] and [11, 14]. Still not enough.
Fourth Iteration: Since 5 is too small and 6 is a possible solution but might not be the smallest one, we must check now if 6 really is the smallest. We check dist = 6 directly as there are no other integers between 5 and 6. We reaffirm there are three pairs [1, 6], [6, 11], and [11, 14].

Since we cannot find a smaller distance that gives us at least k pairs, we conclude that the 3rd smallest distance is indeed 6.

Hence, following the approach outlined, we successfully applied a binary search on the range of distances, utilizing a sorted array and a counting function, to identify the 3rd smallest distance between two elements in the array nums = [1, 6, 11, 14], which is 6.

Solution Implementation

1from bisect import bisect_left
2
3class Solution:
4    def smallestDistancePair(self, nums: List[int], k: int) -> int:
5        # Helper function to count the number of pairs with distance less than or equal to 'dist'
6        def count_pairs_with_max_distance(dist):
7            count = 0
8            # Iterate over the sorted list of numbers
9            for i, upper_bound in enumerate(nums):
10                # Find lower bound such that upper_bound - lower_bound <= dist
11                lower_bound = upper_bound - dist
12                # Find the first position where lower_bound can be inserted to maintain sorted order
13                insertion_point = bisect_left(nums, lower_bound, 0, i)
14                # Accumulate the count of pairs where the distance is less than or equal to 'dist'
15                count += i - insertion_point
16            return count
17
18        nums.sort()  # First, sort the numbers to make it easier to find pairs
19
20        # The maximum possible distance is the difference between the largest and smallest numbers
21        max_possible_distance = nums[-1] - nums[0]
22      
23        # Binary search for the smallest distance such that there are at least 'k' pairs with that distance or less
24        # The search is conducted over the range of possible distances
25        smallest_distance = bisect_left(range(max_possible_distance + 1), k, key=count_pairs_with_max_distance)
26      
27        return smallest_distance
28
29# Note: `List[int]` should be imported from typing module if type hints are used.
30

1class Solution {
2  
3    // Function to calculate the kth smallest distance pair.
4    public int smallestDistancePair(int[] nums, int k) {
5        // First, sort the array to make distances easier to manage.
6        Arrays.sort(nums);
7      
8        // Initialize binary search bounds.
9        int left = 0;
10        int right = nums[nums.length - 1] - nums[0];
11      
12        // Perform binary search to find the smallest distance.
13        while (left < right) {
14            // Find the middle distance.
15            int mid = (left + right) >> 1;
16          
17            // Count the number of pairs with distance less than or equal to mid.
18            if (countPairsWithMaxDistance(mid, nums) >= k) {
19                // If count is greater than or equal to k, narrow the search to the left half.
20                right = mid;
21            } else {
22                // Otherwise, narrow the search to the right half.
23                left = mid + 1;
24            }
25        }
26      
27        // The left boundary will be the result when search is narrowed down to one element.
28        return left;
29    }
30
31    // Helper function to count pairs with maximum distance "dist".
32    private int countPairsWithMaxDistance(int dist, int[] nums) {
33        int count = 0;
34      
35        // Iterate over the array to count pairs.
36        for (int i = 0; i < nums.length; ++i) {
37            // Perform a binary search for the index of the first element in the array
38            // that is within the desired distance from nums[i].
39            int left = 0;
40            int right = i;
41          
42            while (left < right) {
43                // Calculate mid index.
44                int mid = (left + right) >> 1;
45              
46                // Calculate the target distance.
47                int target = nums[i] - dist;
48              
49                // Narrow down the search based on the distance to the target.
50                if (nums[mid] >= target) {
51                    right = mid;
52                } else {
53                    left = mid + 1;
54                }
55            }
56            // Count the number of pairs with a difference of at most "dist" for current index "i".
57            count += i - left;
58        }
59      
60        return count;
61    }
62}
63

1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6    // This function computes the k-th smallest distance pair in a list of integers.
7    int smallestDistancePair(vector<int>& nums, int k) {
8        // First, the array is sorted to calculate distances between pairs efficiently.
9        sort(nums.begin(), nums.end());
10
11        // Initialize binary search bounds. The smallest distance can be zero,
12        // and the largest possible distance is between the smallest and largest element.
13        int left = 0;
14        int right = nums.back() - nums.front();
15
16        // Perform a binary search to find the k-th smallest distance.
17        while (left < right) {
18            int mid = (left + right) >> 1; // Equivalent to dividing by 2.
19
20            // If the count of distances less than or equal to mid is greater than or equal to k,
21            // we adjust the right bound.
22            if (countPairsWithDistance(nums, mid) >= k)
23                right = mid;
24            else // Otherwise, we adjust the left bound.
25                left = mid + 1;
26        }
27
28        // Once left meets right, we've found the smallest distance.
29        return left;
30    }
31
32private:
33    // Helper method to count the number of pairs with distance less than or equal to "dist".
34    int countPairsWithDistance(const vector<int>& nums, int dist) {
35        int count = 0;
36        for (int i = 0; i < nums.size(); ++i) {
37            // For each number, find the first number that is not more than "dist" away
38            // from the current number by using lower_bound.
39            int target = nums[i] - dist;
40            int j = lower_bound(nums.begin(), nums.end(), target) - nums.begin();
41
42            // Add the number of valid pairs found with this distance.
43            count += i - j;
44        }
45        return count;
46    }
47};
48

1function smallestDistancePair(nums: number[], k: number): number {
2    // Sort the input array in ascending order.
3    nums.sort((a, b) => a - b);
4
5    // Store the length of nums array.
6    const n = nums.length;
7
8    // Initialize left pointer to the smallest distance
9    // and right pointer to the largest distance.
10    let left = 0;
11    let right = nums[n - 1] - nums[0];
12
13    // Use binary search to find the kth smallest distance.
14    while (left < right) {
15        // Calculate the mid value as the average of left and right.
16        let mid = left + ((right - left) >> 1);
17        let count = 0; // Initialize the counter for pairs within distance.
18        let start = 0; // Start pointer for the sliding window.
19
20        // Iterate over the nums array using a sliding window approach.
21        for (let end = 0; end < n; end++) {
22            // Increment the start pointer to maintain a maximum distance of mid
23            // between start and end pointers.
24            while (nums[end] - nums[start] > mid) {
25                start++;
26            }
27            // Count pairs with distance less than or equal to mid.
28            count += end - start;
29        }
30
31        // If the number of distances less than or equal to mid is at least k,
32        // narrow the range to the left half (search for a smaller distance).
33        if (count >= k) {
34            right = mid;
35        } else {
36            // Otherwise, narrow the range to the right half (search for a larger distance).
37            left = mid + 1;
38        }
39    }
40
41    // When left and right converge, left (or right) is the kth smallest distance.
42    return left;
43}
44

Time and Space Complexity

The time complexity of the given code mainly consists of two parts: the sorting of the nums list and the binary search which uses the count function at each step.

Sorting the list nums involves a time complexity of O(N log N), where N is the number of elements in nums.
The binary search is performed on a range from 0 to nums[-1] - nums[0], which might seem like it could have a maximum of N possible values (if all numbers in nums are distinct). There are log(N) iterations due to the binary search process.
At each step of the binary search, we invoke the count function. The count function itself has a time complexity of O(N) since it involves iterating over nums to calculate the count of pairs with a distance less than or equal to dist.

Combining these, the total time complexity of the main binary search loop is O(N log N) for the binary search multiplied by the O(N) complexity of the count function, that is O(N log N * N), or simply O(N^2 log N).

The space complexity of the algorithm is O(1) if we exclude the input and the space used for sorting nums, which is typically O(log N) for the sort stack space in the case of efficient sorting algorithms like Timsort used in Python's sorted() function. Otherwise, including the space used for sorting, it would be O(N) if we consider that sorting might be done out-of-place requiring additional space proportional to the input size.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12

1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

<=, left, right

<, left, right

<=, right, left

<, right, left

I don't know