Find K-th Smallest Pair Distance

Hard

#0673Time: O(N^2 log(N^2)), which simplifies to O(N^2 log N). There are O(N^2) pairs to generate. Sorting a list of size O(N^2) takes O(N^2 log(N^2)) time.Space: O(N^2), where N is the number of elements in `nums`. This is required to store all the pair distances in a list.2 companies

Patterns

Two Pointers

Algorithms

Binary Search Sorting

Data structures

Array

Companies

Flipkart Pinterest

Prompt

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 k^th 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 1st 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 <= 10⁴
0 <= nums[i] <= 10⁶
1 <= k <= n * (n - 1) / 2

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves generating all possible pair distances, storing them in a list, sorting the list, and then picking the k-th element. It is the most straightforward solution but also the least efficient.

Algorithm

Initialize an empty list, distances.
Use nested loops to iterate through all unique pairs of indices (i, j) where i < j.
For each pair (nums[i], nums[j]), calculate the distance d = Math.abs(nums[i] - nums[j]).
Add this distance d to the distances list.
After iterating through all pairs, sort the distances list in ascending order.
The k-th smallest distance is the element at index k - 1 of the sorted list.

Walkthrough

The brute-force method is the most intuitive way to solve this problem. We simply follow the problem definition: find all pair distances, then find the k-th smallest among them.

The algorithm proceeds as follows:

Initialize an empty list, for example, distances, to store the absolute differences between pairs of numbers.
Use nested loops to iterate through all unique pairs of indices (i, j) where i < j.
For each pair (nums[i], nums[j]), calculate the distance d = Math.abs(nums[i] - nums[j]).
Add this distance d to the distances list.
After iterating through all pairs, the distances list will contain all N * (N - 1) / 2 pair distances.
Sort the distances list in ascending order.
The k-th smallest distance is the element at index k - 1 of the sorted list.

1import java.util.ArrayList;2import java.util.Collections;3import java.util.List;4 5class Solution {6    public int smallestDistancePair(int[] nums, int k) {7        int n = nums.length;8        List<Integer> distances = new ArrayList<>();9        for (int i = 0; i < n; i++) {10            for (int j = i + 1; j < n; j++) {11                distances.add(Math.abs(nums[i] - nums[j]));12            }13        }14        Collections.sort(distances);15        return distances.get(k - 1);16    }17}

This approach is simple but inefficient due to the large number of pairs, which can be up to approximately 5 * 10^7 for N = 10^4. Sorting this many elements is computationally expensive and will not pass the given constraints.

Complexity

Time

O(N^2 log(N^2)), which simplifies to O(N^2 log N). There are O(N^2) pairs to generate. Sorting a list of size O(N^2) takes O(N^2 log(N^2)) time.

Space

O(N^2), where N is the number of elements in `nums`. This is required to store all the pair distances in a list.

Trade-offs

Pros

Simple to understand and implement.

Cons

Highly inefficient for large inputs due to its high time complexity.
Requires a large amount of memory to store all pair distances, which can lead to Memory Limit Exceeded errors.

This is a highly efficient approach that leverages the properties of the problem. Instead of finding the distances directly, we can binary search for the k-th smallest distance value. The key idea is to guess a distance d and then efficiently count how many pairs have a distance less than or equal to d.

Algorithm

First, sort the input array nums.
Define the search space for the binary search. The smallest possible distance is 0, and the largest is nums[n-1] - nums[0]. Let low = 0 and high = nums[n-1] - nums[0].
Perform a binary search on the range [low, high]. For each mid value (a potential answer):
- Count the number of pairs (nums[i], nums[j]) with nums[j] - nums[i] <= mid. This can be done in O(N) time using a two-pointer/sliding window technique on the sorted array.
- Let this count be count.
- If count >= k, it means mid might be our answer, or the actual answer is even smaller. So, we record mid as a potential answer and try to find a smaller one by setting high = mid - 1.
- If count < k, it means mid is too small to be the k-th distance. We need to look for a larger distance, so we set low = mid + 1.
The last recorded potential answer will be the smallest distance d for which there are at least k pairs with distance <= d, which is the k-th smallest distance.

Walkthrough

A much more efficient solution involves binary searching for the answer. The possible distances are bounded between 0 and max(nums) - min(nums). We can binary search within this range. For any given distance d, we need to be able to efficiently count how many pairs have a distance less than or equal to d. If this count is at least k, then the k-th smallest distance is d or smaller. Otherwise, it must be larger than d.

The countPairs function, which counts pairs with distance <= mid, can be implemented efficiently using a two-pointer (or sliding window) approach on the sorted array in O(N) time.

Initialize count = 0 and a right pointer right = 0.
Iterate with a left pointer left from 0 to n-1.
For each left, advance right such that nums[right] - nums[left] <= mid.
The number of valid pairs for the current left is right - left - 1. Add this to the total count.

1import java.util.Arrays;2 3class Solution {4    public int smallestDistancePair(int[] nums, int k) {5        Arrays.sort(nums);6        int n = nums.length;7        int low = 0;8        int high = nums[n - 1] - nums[0];9        int ans = 0;10 11        while (low <= high) {12            int mid = low + (high - low) / 2;13            // Count pairs with distance <= mid14            if (countPairs(nums, mid) >= k) {15                ans = mid; // This is a potential answer16                high = mid - 1; // Try for a smaller distance17            } else {18                low = mid + 1; // Distance is too small19            }20        }21        return ans;22    }23 24    // Counts pairs with distance <= mid in O(N)25    private int countPairs(int[] nums, int mid) {26        int count = 0;27        int n = nums.length;28        int right = 0;29        for (int left = 0; left < n; ++left) {30            // While the condition is met, move the right pointer31            while (right < n && nums[right] - nums[left] <= mid) {32                right++;33            }34            // For nums[left], all elements from nums[left+1] to nums[right-1] form a valid pair.35            // The number of such elements is (right - 1) - (left + 1) + 1 = right - left - 1.36            count += right - left - 1;37        }38        return count;39    }40}

Complexity

Time

O(N log N + N log W), where N is the length of `nums` and W is the difference between the maximum and minimum values in `nums`. O(N log N) is for the initial sort. The binary search runs O(log W) times, and each time we do an O(N) scan (the `countPairs` function).

Space

O(log N) or O(N), depending on the implementation of the sorting algorithm. If we are allowed to modify the input array, it can be O(log N) for the recursion stack. Otherwise, O(N) for a copy.

Trade-offs

Pros

Very efficient and passes the time limits for the given constraints.
It cleverly transforms the problem from finding an element to a decision problem, which is a common and powerful technique.

Cons

More complex to understand and implement compared to the brute-force approach.
Requires a good grasp of binary search on the answer and the two-pointer technique.

Solutions

Solution

1class Solution {2public3  int smallestDistancePair(int[] nums, int k) {4    Arrays.sort(nums);5    int left = 0, right = nums[nums.length - 1] - nums[0];6    while (left < right) {7      int mid = (left + right) >> 1;8      if (count(mid, nums) >= k) {9        right = mid;10      } else {11        left = mid + 1;12      }13    }14    return left;15  }16private17  int count(int dist, int[] nums) {18    int cnt = 0;19    for (int i = 0; i < nums.length; ++i) {20      int left = 0, right = i;21      while (left < right) {22        int mid = (left + right) >> 1;23        int target = nums[i] - dist;24        if (nums[mid] >= target) {25          right = mid;26        } else {27          left = mid + 1;28        }29      }30      cnt += i - left;31    }32    return cnt;33  }34}

1/** * @param {number[]} nums * @param {number} k * @return {number} */ function smallestDistancePair(2  nums,3  k,4) {5  nums.sort((a, b) => a - b);6  const n = nums.length;7  let left = 0,8    right = nums[n - 1] - nums[0];9  while (left < right) {10    const mid = (left + right) >> 1;11    let count = 0,12      i = 0;13    for (let j = 0; j < n; j++) {14      while (nums[j] - nums[i] > mid) {15        i++;16      }17      count += j - i;18    }19    if (count >= k) {20      right = mid;21    } else {22      left = mid + 1;23    }24  }25  return left;26}

1class Solution {2public:3  int smallestDistancePair(vector<int> &nums, int k) {4    sort(nums.begin(), nums.end());5    int left = 0, right = nums.back() - nums.front();6    while (left < right) {7      int mid = (left + right) >> 1;8      if (count(mid, k, nums) >= k)9        right = mid;10      else11        left = mid + 1;12    }13    return left;14  }15  int count(int dist, int k, vector<int> &nums) {16    int cnt = 0;17    for (int i = 0; i < nums.size(); ++i) {18      int target = nums[i] - dist;19      int j = lower_bound(nums.begin(), nums.end(), target) - nums.begin();20      cnt += i - j;21    }22    return cnt;23  }24};

1class Solution:2    def smallestDistancePair(self, nums: List[int], k: int) -> int: def count(dist): cnt = 0 for i, b in enumerate(nums): a = b - dist j = bisect_left(nums, a, 0, i) cnt += i - j return cnt nums . sort() return bisect_left(range(nums[- 1] - nums[0]), k, key=count)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem