719. Find K-th Smallest Pair Distance

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

Approach 01:

#include <algorithm>
#include <vector>

using namespace std;

class Solution {
public:
    // Function to find the k-th smallest distance pair
    int smallestDistancePair(vector<int>& nums, int k) {
        ranges::sort(nums);

        int left = 0;
        int right = nums.back() - nums.front();

        // Binary search for the smallest distance
        while (left < right) {
            const int middle = (left + right) / 2;
            if (countPairsWithDistanceNoGreaterThan(nums, middle) >= k)
                right = middle;
            else
                left = middle + 1;
        }

        return left;
    }

private:
    // Function to count pairs with distance no greater than maxDistance
    int countPairsWithDistanceNoGreaterThan(const vector<int>& nums,
                                            int maxDistance) {
        int pairCount = 0;
        int j = 1;

        // For each index i, find the first index j such that nums[j] > nums[i] + maxDistance
        for (int i = 0; i < nums.size(); ++i) {
            while (j < nums.size() && nums[j] <= nums[i] + maxDistance)
                ++j;
            pairCount += j - i - 1;
        }
        return pairCount;
    }
};

class Solution:
    def smallestDistancePair(self, nums, k):
        nums.sort()

        left = 0
        right = nums[-1] - nums[0]

        # Binary search for the smallest distance
        while left < right:
            middle = (left + right) // 2
            if self.countPairsWithDistanceNoGreaterThan(nums, middle) >= k:
                right = middle
            else:
                left = middle + 1

        return left

    # Function to count pairs with distance no greater than maxDistance
    def countPairsWithDistanceNoGreaterThan(self, nums, maxDistance):
        pairCount = 0
        j = 1

        # For each index i, find the first index j such that nums[j] > nums[i] + maxDistance
        for i in range(len(nums)):
            while j < len(nums) and nums[j] <= nums[i] + maxDistance:
                j += 1
            pairCount += j - i - 1

        return pairCount

Time Complexity

• Sorting:

  The initial sorting of the array takes \( O(n \log n) \), where \( n \) is the number of elements in nums.

• Binary Search:

  The binary search runs in \( O(\log d) \) time, where \( d \) is the range of distances (i.e., the difference between the maximum and minimum elements in nums).

• Counting Pairs:

  The countPairsWithDistanceNoGreaterThan function is called within the binary search loop. Each call to this function involves iterating over the array, which takes \( O(n) \) time.

• Overall Time Complexity:

  The overall time complexity is \( O(n \log n + n \log d) \) due to sorting and the binary search process.

Space Complexity

• Sorting:

  The sorting operation requires \( O(1) \) additional space if done in-place, or \( O(n) \) if not.

• Overall Space Complexity:

  The overall space complexity is \( O(1) \), assuming in-place sorting. Otherwise, it is \( O(n) \).