719. 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.

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.

Note:

2 <= len(nums) <= 10000.
0 <= nums[i] < 1000000.
1 <= k <= len(nums) * (len(nums) - 1) / 2.

Problem Summary #

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

Notes:

2 <= len(nums) <= 10000.
0 <= nums[i] < 1000000.
1 <= k <= len(nums) * (len(nums) - 1) / 2.

Solution Ideas #

Given an array, find the k-th smallest value among the differences between every pair of elements. The differences between pairs of elements may be repeated; repeated differences are counted multiple times and are not deduplicated.
This problem can be solved with binary search. First sort the original array, then the maximum difference is nums[len(nums)-1] - nums[0], and the minimum difference is 0, so search for the final answer in the interval [0, nums[len(nums)-1] - nums[0]]. For each mid, determine how many differences are less than or equal to mid. The problem is then transformed into finding a number in the array such that the number of combinations satisfying nums[i] - nums[j] ≤ mid equals k. So how to calculate the total number of pairs whose difference is less than mid is the key to this problem.
The most brute-force method is a double loop to count directly. This method is inefficient and takes a long time. The reason is that it does not use the condition that the array is sorted. In fact, the sorted array helps calculate the number of combinations that satisfy the condition. Use two pointers and a sliding window to calculate the total number of combinations. See Solution 1.

Code #


package leetcode

import (
	"sort"
)

func smallestDistancePair(nums []int, k int) int {
	sort.Ints(nums)
	low, high := 0, nums[len(nums)-1]-nums[0]
	for low < high {
		mid := low + (high-low)>>1
		tmp := findDistanceCount(nums, mid)
		if tmp >= k {
			high = mid
		} else {
			low = mid + 1
		}
	}
	return low
}

// Solution 1: Two pointers
func findDistanceCount(nums []int, num int) int {
	count, i := 0, 0
	for j := 1; j < len(nums); j++ {
		for nums[j]-nums[i] > num && i < j {
			i++
		}
		count += (j - i)
	}
	return count
}

// Solution 2: Brute-force search
func findDistanceCount1(nums []int, num int) int {
	count := 0
	for i := 0; i < len(nums); i++ {
		for j := i + 1; j < len(nums); j++ {
			if nums[j]-nums[i] <= num {
				count++
			}
		}
	}
	return count
}