n^2 pairs takes n^2 log n time again, and space complexity is also O(n).

Calculate the distances. Lets take nums = [1, 3, 4, 7, 8], and k = 3 ⇨ O(n^2) time
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
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]
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

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