Find K-th Smallest Pair Distance

Given an integer array, return the k-th smallestdistanceamong all the pairs. The distance of a pair (A, B) is defined as the absolute difference between A and B.

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.

Solution

Approach #1: Heap

Intuition and Algorithm

Sort the points. For every point with indexi, the pairs with indexes(i, j)[by order of distance] are(i, i+1), (i, i+2), ..., (i, N-1).

Let's keep a heap of pairs, initiallyheap = [(i, i+1) for all i], and ordered by distance (the distance of(i, j)isnums[j] - nums[i].) Whenever we use a pair(i, x)from our heap, we will add(i, x+1)to our heap when appropriate.

Complexity Analysis

• Time Complexity:O((k+N)logN)O((k+N)logN), whereNNis the length ofnums. Ask=O(N2)k=O(N​2​​), this isO(N2logN)O(N​2​​logN)in the worst case. The complexity added by our heap operations is eitherO((k+N)logN)O((k+N)logN)in the Java solution, orO(klogN+N)O(klogN+N)in the Python solution because theheapq.heapifyoperation is linear time. Additionally, we addO(NlogN)O(NlogN)complexity due to sorting.

• Space Complexity:O(N)O(N), the space used to store ourheapof at mostN-1elements.

class Solution {
    public int smallestDistancePair(int[] nums, int k) {
        Arrays.sort(nums);
        PriorityQueue<Node> heap = new PriorityQueue<Node>(nums.length,
            Comparator.<Node> comparingInt(node -> nums[node.nei] - nums[node.root]));
        for (int i = 0; i + 1 < nums.length; ++i) {
            heap.offer(new Node(i, i+1));
        }

        Node node = null;
        for (; k > 0; --k) {
            node = heap.poll();
            if (node.nei + 1 < nums.length) {
                heap.offer(new Node(node.root, node.nei + 1));
            }
        }
        return nums[node.nei] - nums[node.root];
    }
}
class Node {
    int root;
    int nei;
    Node(int r, int n) {
        root = r;
        nei = n;
    }
}

Approach #2: Binary Search + Prefix Sum

Intuition

Let's binary search for the answer. It's definitely in the range[0, W], whereW = max(nums) - min(nums)].

Letpossible(guess)be true if and only if there arekor more pairs with distance less than or equal toguess. We will focus on evaluating ourpossiblefunction quickly.

Algorithm

Letprefix[v]be the number of points innumsless than or equal tov. Also, letmultiplicity[j]be the number of pointsiwithi < j and nums[i] == nums[j]. We can record both of these with a simple linear scan.

Now, for every pointi, the number of pointsjwithi < jandnums[j] - nums[i] <= guessisprefix[x+guess] - prefix[x] + (count[i] - multiplicity[i]), wherecount[i]is the number of ocurrences ofnums[i]innums. The sum of this over alliis the number of pairs with distance<= guess.

Finally, because the sum ofcount[i] - multiplicity[i]is the same as the sum ofmultiplicity[i], we could just replace that term withmultiplicity[i]without affecting the answer. (Actually, the sum of multiplicities in total will be a constant used in the answer, so we could precalculate it if we wanted.)

In our Java solution, we computedpossible = count >= kdirectly in the binary search instead of using a helper function.

Complexity Analysis

• Time Complexity:O(W+NlogW+NlogN)O(W+NlogW+NlogN), whereNNis the length ofnums, andWWis equal tonums[nums.length - 1] - nums[0]. We doO(W)O(W)work to calculateprefixinitially. ThelogWlogWfactor comes from our binary search, and we doO(N)O(N)work inside our call topossible(or to calculatecountin Java). The finalO(NlogN)O(NlogN)factor comes from sorting.

• Space Complexity:O(N+W)O(N+W), the space used to storemultiplicityandprefix.

class Solution {
    public int smallestDistancePair(int[] nums, int k) {
        Arrays.sort(nums);
        int WIDTH = 2 * nums[nums.length - 1];

        //multiplicity[i] = number of nums[j] == nums[i] (j < i)
        int[] multiplicity = new int[nums.length];
        for (int i = 1; i < nums.length; ++i) {
            if (nums[i] == nums[i-1]) {
                multiplicity[i] = 1 + multiplicity[i - 1];
            }
        }

        //prefix[v] = number of values <= v
        int[] prefix = new int[WIDTH];
        int left = 0;
        for (int i = 0; i < WIDTH; ++i) {
            while (left < nums.length && nums[left] == i) left++;
            prefix[i] = left;
        }

        int lo = 0;
        int hi = nums[nums.length - 1] - nums[0];
        while (lo < hi) {
            int mi = (lo + hi) / 2;
            int count = 0;
            for (int i = 0; i < nums.length; ++i) {
                count += prefix[nums[i] + mi] - prefix[nums[i]] + multiplicity[i];
            }
            //count = number of pairs with distance <= mi
            if (count >= k) hi = mi;
            else lo = mi + 1;
        }
        return lo;
    }
}

Approach #3: Binary Search + Sliding Window

Intuition

As inApproach #2, let's binary search for the answer, and we will focus on evaluating ourpossiblefunction quickly.

Algorithm

We will use a sliding window approach to count the number of pairs with distance<=guess.

For every possibleright, we maintain the loop invariant:leftis the smallest value such thatnums[right] - nums[left] <= guess. Then, the number of pairs withrightas it's right-most endpoint isright - left, and we add all of these up.

Complexity Analysis

• Time Complexity:O(NlogW+NlogN)O(NlogW+NlogN), whereNNis the length ofnums, andWWis equal tonums[nums.length - 1] - nums[0]. ThelogWlogWfactor comes from our binary search, and we doO(N)O(N)work inside our call topossible(or to calculatecountin Java). The finalO(NlogN)O(NlogN)factor comes from sorting.

• Space Complexity:O(1)O(1). No additional space is used except for integer variables.

class Solution {
    public int smallestDistancePair(int[] nums, int k) {
        Arrays.sort(nums);

        int lo = 0;
        int hi = nums[nums.length - 1] - nums[0];
        while (lo < hi) {
            int mi = (lo + hi) / 2;
            int count = 0, left = 0;
            for (int right = 0; right < nums.length; ++right) {
                while (nums[right] - nums[left] > mi)  {
                    left++;
                }
                count += right - left;
            }
            //count = number of pairs with distance <= mi
            if (count >= k) {
                hi = mi;
            } else {
                lo = mi + 1;
            }
        }
        return lo;
    }
}