LeetCode - Find K-th Smallest Pair Distance

https://leetcode.com/problems/find-k-th-smallest-pair-distance/

Problem

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

Solution

There is a brute forced solution which is generate all pair-distance and maintain a heap with O(k) elements, which i think will TLE. The time complexity is O(n^2 * logK) which can be converted into O(n^2 log(n^2)).

My first solution is: try to find the smallest distance that has more than or equal k smaller pair-distance.

1
2
3
4
5
6
for distance := range(0, 1000000) { //minDistance -> maxDistance
cnt := countSmallerOrEqualPairDistance(distance)
if cnt >= k {
return cnt
}
}

There are 3 things we need to consider here:

  1. Why smallest distance is the correct answer?
  2. How can we optimize the distance for loop?
  3. What is the best way to implement countSmallerOrEqualPairDistance?

Answers:

  1. “Why smallest distance is the correct answer?”. We have to do some math here:

    • Assumed we have the sorted array diff which is all pair distance: diff[0] <= diff[1] <= ... <= diff[k] <= diff[k+1] <= .. <= diff[N*(N-1)/2] where (N is length of input array)
    • The distance is going from 0 -> maxDistance, the first distance satisfies cnt := countSmallerOrEqualPairDistance(distance) >= k will be in in the range [diff[k], diff[k+1]) since if cnt < diff[k] then there are less than k pair distances smaller than cnt. The same as, if cnt >= diff[k+1] there will be more than k pair distance smaller than cnt.
    • => The smallest distance is the result.
  2. “How can we optimize the distance for loop?”. As proof in the first question 1, there is a linear attribute when finding distance. We can use binary search to find the smallest distance.

  3. “What is the best way to implement countSmallerOrEqualPairDistance(distance)?”. We can first sort the input array nums. For each position i in nums, we find the farest position j on the right which is nums[j] - nums[i] <= distance. There are three solutions:

    • We can do the O(N^2) count here. Which caused the final time complexity O(N^2Log(MaxDiff)). It’s slightly better than the brute forced solution since MaxDiff < N^2.
    • For each position i, using binary search to find the farest j. This solution has O(NlogN) time complexity, the final time complexity is O(NlogNlogMaxDiff) which enough to get accepted.
    • The best solution here is that using two pointers:
      • We can maintain the farest j for the current i.
      • We can easily see that, if i += 1, j will stay the same or move to the right.
      • => For each position, we only traverse thought 2 times.
      • => Time complexity is O(N) which leads to final time complexity is O(N*logMaxDiff)

Code for binary search solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
func smallestDistancePair(nums []int, k int) int {
sort.SliceStable(nums, func(i, j int) bool {
return nums[i] < nums[j]
})

le, ri := 0, nums[len(nums)-1] - nums[0]
res := 0
for le <= ri {
mid := le + (ri - le) / 2
smallerPairs := countSmallerOrEqualPairs(nums, mid)

if smallerPairs >= k {
res = mid
}

if smallerPairs < k {
le = mid + 1
} else {
ri = mid - 1
}
}
return res
}

func countSmallerOrEqualPairs(nums []int, value int) int {
cnt := 0
for i := 0; i < len(nums); i++ {
le, ri := i, len(nums)-1
j := i
for le <= ri {
mid := le + (ri-le)/2
if nums[mid] - nums[i] <= value {
j = mid
le = mid + 1
} else {
ri = mid - 1
}
}
cnt += j-i
}
return cnt
}

Code for two pointer solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
func smallestDistancePair(nums []int, k int) int {
sort.SliceStable(nums, func(i, j int) bool {
return nums[i] < nums[j]
})

le, ri := 0, nums[len(nums)-1] - nums[0]
res := 0
for le <= ri {
mid := le + (ri - le) / 2
smallerPairs := countSmallerOrEqualPairs(nums, mid)

if smallerPairs >= k {
res = mid
}

if smallerPairs < k {
le = mid + 1
} else {
ri = mid - 1
}
}
return res
}

func countSmallerOrEqualPairs(nums []int, value int) int {
cnt := 0
j := 0
for i := 0; i < len(nums); i++ {
for j+1 < len(nums) && nums[j+1] - nums[i] <= value {
j++
}
cnt += j-i
}
return cnt
}

Support me via: https://ko-fi.com/iamquang95