Problem

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.

Examples

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

Solution

Method 1 - Generate distances and Sort

Using sorting and distances array

The naive approach will be to:

  1. Create the difference pairsbetween the numbers, by using iterator pair (i, j) where 0 <= i < j < nums.length. This takes O(n^2) time
  2. Then, save the sort them, and pick the kth smallest pair distance. That takes O(n^2 log n)
  3. Store these distances, takes O(n^2) space.
  4. Sort them, takes O(n log n) time
  5. Return the kth distance

Complexity

  • ⏰ Time complexity: O(n^2 log n)
  • 🧺 Space complexity: O(n^2)

Method 2 - Using the Heap

Instead of using array to store distances, we can use minHeap to do that, keep on picking the k distances. Adding n^2 pairs takes n^2 log n time again, and space complexity is also O(n).

Method 3 - Using bucket Sort

  1. Calculate the distances. Lets take nums = [1, 3, 4, 7, 8], and k = 3 ⇨ O(n^2) time
  2. Create the buckets array of size max(nums) + 1 ⇨ [0, 0, 0, 0, 0, 0, 0, 0, 0], where index is the distance and value is the count or number of times distance occurs
  3. Now, store the count of distances in bucket array. ⇨ O(n^2) space
    • These are the pairs:
      • (1, 3), (1, 4), (1, 7), (1, 8) ⇨ 2, 3, 6, 7
      • (3, 4), (3, 7), (3, 8), ⇨ 1, 4, 5
      • (4, 7), (4, 8), ⇨ 3, 4
      • (7, 8) ⇨ 1
    • We can see that distance 1 occurs twice, distance 2 occurs once, distance 3 twice, distance 4 twice and so on.
    • Here is the buckets array: [0, 2, 1, 2, 2, 1, 1, 1, 0]
  4. Now start iterating on buckets array from left to right, and reduce k - buckets[i], and as soon as k ≤ 0, we get the answer. ⇨ O(n^2) time
    • For eg. we start with index 0, value is 0
    • Then we go to index 1, k -= 2 ⇨ k = 1
    • Then we go to index 2, k -= 1 = 0 ⇨ distance 2 is our answer

Method 4 - Using Binary Search and Two Pointer Technique

Here are the steps we can take:

  1. Sort the array: Sorting the array helps in efficiently finding the distance between pairs using two pointers.
  2. Binary search for the distance: Use binary search to guess the (k)-th smallest distance. Start with a range that goes from the smallest possible distance (0) to the largest possible distance (the difference between the maximum and minimum elements in the sorted array).
  3. Count pairs with distance less than or equal to the midpoint: For each guess (midpoint) in the binary search, count how many pairs in the array have a distance less than or equal to this midpoint. Use a two-pointer technique for this step.
  4. Adjust the search range based on the count: If the count of pairs with a distance less than or equal to the midpoint is greater than or equal to (k), move the upper bound of the search range to the midpoint. Otherwise, move the lower bound to the midpoint + 1.
  5. Convergence: When the search range converges, the lower bound will be the desired (k)-th smallest distance.

Code

Java
class Solution {
    public int smallestDistancePair(int[] nums, int k) {
        Arrays.sort(nums);
        int low = 0;
        int high = nums[nums.length - 1] - nums[0];
		int ans = 0;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (countPairs(nums, mid) < k) {
                low = mid + 1;
            } else {
	            ans = mid;
                high = mid - 1;
            }
        }
        return ans;
    }
    private int countPairs(int[] nums, int mid) {
        int count = 0, j = 0;
        for (int i = 0; i < nums.length; i++) {
            while (j < nums.length && nums[j] - nums[i] <= mid) {
                j++;
            }
            count += (j - i - 1);
        }
        return count;
    }
}
Python
def smallestDistancePair(nums, k):
    nums.sort()
    low, high = 0, nums[-1] - nums[0]

    while low < high:
        mid = (low + high) // 2
        if countPairs(nums, mid) >= k:
            high = mid
        else:
            low = mid + 1

    return low

def countPairs(nums, mid):
    count = 0
    j = 0
    for i in range(len(nums)):
        while j < len(nums) and nums[j] - nums[i] <= mid:
            j += 1
        count += j - i - 1
    return count

Complexity

  • ⏰ Time complexity: O(n log D + n log n) = O((n + D) * logn)
    • Sorting nums take O(n log n) time
    • Binary search takes O(D) time, where D = max(nums) - min(nums).
    • Then, to countPairs, it takes O(n) time, as it is like a sliding window.
  • 🧺 Space complexity: O(1)

Dry Run

Lets take nums = [1, 3, 4, 7, 8], n = 5 and k = 3.

This is also a sorted array for us. Now, for better understanding, lets write down the pairs with distances:

  • (1, 3), (1, 4), (1, 7), (1, 8) ⇨ 2, 3, 6, 7
  • (3, 4), (3, 7), (3, 8), ⇨ 1, 4, 5
  • (4, 7), (4, 8), ⇨ 3, 4
  • (7, 8) ⇨ 1

We can see distance 3 is kth smallest distance.

Initially, low = 0, high = nums[4] - nums[0] = 8 - 1 = 7.

Iteration 1

mid = 3 ⇨ Count the pairs with distance ≤ 3.

Counting Pairs

  1. For i = 0 (nums[0] = 1):

    • j = 1, nums[j] = 3, distance = 2 (count this pair)
    • j = 2, nums[j] = 4, distance = 3 (count this pair)
    • j = 3, nums[j] = 7, distance = 6 (stop here, distance > 3)
    • Count: (2) pairs, total count so far = 2

  2. For i = 1 (nums[1] = 3):

    • j = 2, nums[j] = 4, distance = 1 (count this pair)
    • j = 3, nums[j] = 7, distance = 4 (stop here, distance > 3)
    • Count: (1) more pair, total count so far = 3

  3. For i = 2 (nums[2] = 4):

    • j = 3, nums[j] = 7, distance = 3 (count this pair)
    • j = 4, nums[j] = 8, distance = 4 (stop here, distance > 3)
    • Count: (1) more pair, total count so far = 4

  4. For i = 3 (nums[3] = 7):

    • j = 4, nums[j] = 8, distance = 1 (count this pair)
    • Total count so far = 5

Since count = 5 is ≥ (k = 3), adjust bounds:

  • high = mid = 3
Iteration 2
  • mid = (low + high) / 2 = (0 + 3) / 2 = 1
  • Count pairs with distance ≤ 1:

Counting Pairs

  1. For i = 0 (nums[0] = 1):
    • j = 1, nums[j] = 3, distance = 2 (stop here, distance > 1)
    • Count: 0 pairs, total count so far = 0
  2. For i = 1 (nums[1] = 3):
    • j = 2, nums[j] = 4, distance = 1 (count this pair)
    • j = 3, nums[j] = 7, distance = 4 (stop here, distance > 1)
    • Count: (1) pair, total count so far = 1
  3. For i = 2 (nums[2] = 4):
    • j = 3, nums[j] = 7, distance = 3 (stop here, distance > 1)
    • Count: 0 pairs, total count so far = 1
  4. For i = 3 (nums[3] = 7):
    • j = 4, nums[j] = 8, distance = 1 (count this pair)
    • Total count so far = 2

Since count = 2 is < (k = 3), adjust bounds:

  • low = mid + 1 = 2
Iteration 3
  • mid = (low + high) / 2 = (2 + 3) / 2 = 2
  • Count pairs with distance ≤ 2:

Counting Pairs

  1. For i = 0 (nums[0] = 1):

    • j = 1, nums[j] = 3, distance = 2 (count this pair)
    • j = 2, nums[j] = 4, distance = 3 (stop here, distance > 2)
    • Count: (1) pair, total count so far = 1

  2. For i = 1 (nums[1] = 3):

    • j = 2, nums[j] = 4, distance = 1 (count this pair)
    • j = 3, nums[j] = 7, distance = 4 (stop here, distance > 2)
    • Count: (1) more pair, total count so far = 2

  3. For i = 2 (nums[2] = 4):

    • j = 3, nums[j] = 7, distance = 3 (stop here, distance > 2)
    • Count: 0 pairs, total count so far = 2

  4. For i = 3 (nums[3] = 7):

    • j = 4, nums[j] = 8, distance = 1 (count this pair)
    • Total count so far = 3

Since count = 3 is equal to (k = 3), adjust bounds:

  • high = mid = 2
Final Result

Output: 2