Find K-th Smallest Pair Distance

HARD

Description

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 1^st 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

Checkout 2 different approaches to solve Find K-th Smallest Pair Distance. Click on different approaches to view the approach and algorithm in detail.

Brute Force with Sorting

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.

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.

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 Analysis

Time Complexity: 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 Complexity: O(N^2), where N is the number of elements in `nums`. This is required to store all the pair distances in a list.

Pros and Cons

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.

Code Solutions

Checking out 4 solutions in different languages for Find K-th Smallest Pair Distance. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Find K-th Smallest Pair Distance

Algorithms:

Binary SearchSorting

Patterns:

Two Pointers

Data Structures:

Array

Companies:

Flipkart |Pinterest |