719. Find K-th Smallest Pair Distance
Problem Description
The goal of this problem is to find the k
th 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. Ifnums
is sorted, any pair of numbers(a, b)
such thatb >= a+d
(whered
is our target distance) contributes to the count of distances that are at leastd
. -
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 ourk
th 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 numberb
innums
, we finda
such thata = b - current_distance
and count all numbers betweena
andb
to get the number of pairs whose distance is at most the current distance we are checking. We use thebisect_left
function to find the first index wherea
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 leastk
.
By combining sorting and binary search, the solution effectively narrows down the exact distance that is the k
th 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
tonums[-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 thek
th smallest pair distance. -
The Count Function: The
count(dist)
function is a helper function that counts how many pairs in the sortednums
array have a distance less than or equal todist
. We do this by iterating over each elementb
in the array and usingbisect_left
to find the first index whereb - dist
could fit (this would be the elementa
). The count of elements from this index toi
(current index ofb
) gives us the number of pairs with one element less than or equal tob - dist
and the other equal tob
. Thereby, the difference between the indices gives us the pairs count with a maximum distance ofdist
. -
Using Bisect to Find the Kth Distance: Finally,
bisect_left
is used on the range of possible distances with ourcount
function as the key. This means that for each potential distancedist
that the binary search is considering,bisect_left
uses thecount
function to determine if the number of pairs with a distance less than or equal todist
is less thank
. If the count is less thank
,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 leastk
.
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 k
th 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 EvaluatorExample 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 is14 - 1 = 13
. -
The Count Function: Now, we need a function to count pairs with distance less than or equal to
dist
. For example, ifdist = 4
, we would find:- Pairs for
b = 6
: None, since noa
exists in[1]
such that6 - a <= 4
. - Pairs for
b = 11
: The element that fits is6
(11 - 6 = 5
is not less than or equal to4
), so there are 0 pairs. - Pairs for
b = 14
: The element that fits is11
(14 - 11 = 3
is less than or equal to4
), so there is 1 pair[11, 14]
.
Thus for
dist = 4
, the count is 1. - Pairs for
-
Using Bisect to Find the Kth Distance: We apply a binary search (using
bisect_left
) to the range[0, 13]
to find the smallest distancedist
such that there are at leastk = 3
pairs with distance less than or equal todist
.
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 to6
. Using the count function, we find there are three pairs with distances less than or equal to6
:[1, 6]
,[6, 11]
, and[11, 14]
. Since we have found exactly 3 pairs, we knowdist = 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 thek = 3
condition. We check left of6
, usingmid = (0 + 6) / 2 = 3
. The pairs with distance less than or equal to3
are[11, 14]
, so just one pair, which is not enough. -
Third Iteration: Since
3
is too small, we now check between4
and6
. Letmid = (4 + 6) / 2 = 5
. Now, the count function returns two pairs with distances less than or equal to5
:[1, 6]
and[11, 14]
. Still not enough. -
Fourth Iteration: Since
5
is too small and6
is a possible solution but might not be the smallest one, we must check now if6
really is the smallest. We checkdist = 6
directly as there are no other integers between5
and6
. 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 ofO(N log N)
, whereN
is the number of elements innums
. -
The binary search is performed on a range from 0 to
nums[-1] - nums[0]
, which might seem like it could have a maximum ofN
possible values (if all numbers innums
are distinct). There arelog(N)
iterations due to the binary search process. -
At each step of the binary search, we invoke the
count
function. Thecount
function itself has a time complexity ofO(N)
since it involves iterating overnums
to calculate the count of pairs with a distance less than or equal todist
.
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.
Which type of traversal does breadth first search do?
Recommended Readings
Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers div class responsive iframe iframe src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe div Two pointers is a common interview
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.