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]

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:

Sort the array: Sorting the array helps in efficiently finding the distance between pairs using two pointers.
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).
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.
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.
Convergence: When the search range converges, the lower bound will be the desired (k)-th smallest distance.

Code

[{"language":"Java","code":"class Solution {\n    public int smallestDistancePair(int[] nums, int k) {\n        Arrays.sort(nums);\n        int low = 0;\n        int high = nums[nums.length - 1] - nums[0];\n\t\tint ans = 0;\n        while (low <= high) {\n            int mid = (low + high) / 2;\n            if (countPairs(nums, mid) < k) {\n                low = mid + 1;\n            } else {\n\t            ans = mid;\n                high = mid - 1;\n            }\n        }\n        return ans;\n    }\n    private int countPairs(int[] nums, int mid) {\n        int count = 0, j = 0;\n        for (int i = 0; i < nums.length; i++) {\n            while (j < nums.length && nums[j] - nums[i] <= mid) {\n                j++;\n            }\n            count += (j - i - 1);\n        }\n        return count;\n    }\n}","lang":"java","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">class</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> Solution</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">    public</span><span style=\"color:#D73A49;--shiki-dark:#F97583\"> int</span><s

Related Tags