Scale Engineer

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 SearchSorting
Data structures
Array
Companies
FlipkartPinterest

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 kth 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 <= 104
  • 0 <= nums[i] <= 106
  • 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:

  1. Initialize an empty list, for example, distances, to store the absolute differences between pairs of numbers.
  2. Use nested loops to iterate through all unique pairs of indices (i, j) where i < j.
  3. For each pair (nums[i], nums[j]), calculate the distance d = Math.abs(nums[i] - nums[j]).
  4. Add this distance d to the distances list.
  5. After iterating through all pairs, the distances list will contain all N * (N - 1) / 2 pair distances.
  6. Sort the distances list in ascending order.
  7. The k-th smallest distance is the element at index k - 1 of the sorted list.
import java.util.ArrayList;import java.util.Collections;import java.util.List; class Solution {    public int smallestDistancePair(int[] nums, int k) {        int n = nums.length;        List<Integer> distances = new ArrayList<>();        for (int i = 0; i < n; i++) {            for (int j = i + 1; j < n; j++) {                distances.add(Math.abs(nums[i] - nums[j]));            }        }        Collections.sort(distances);        return distances.get(k - 1);    }}

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.

Solutions

class Solution {public  int smallestDistancePair(int[] nums, int k) {    Arrays.sort(nums);    int left = 0, right = nums[nums.length - 1] - nums[0];    while (left < right) {      int mid = (left + right) >> 1;      if (count(mid, nums) >= k) {        right = mid;      } else {        left = mid + 1;      }    }    return left;  }private  int count(int dist, int[] nums) {    int cnt = 0;    for (int i = 0; i < nums.length; ++i) {      int left = 0, right = i;      while (left < right) {        int mid = (left + right) >> 1;        int target = nums[i] - dist;        if (nums[mid] >= target) {          right = mid;        } else {          left = mid + 1;        }      }      cnt += i - left;    }    return cnt;  }}

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 →

Next problem