Find K-th Smallest Pair Distance solution and explanation
Google
9 more videos on this problem
Find K-th Smallest Pair Distance - Leetcode 719 - PythonNeetCodeIO · 25:35 · 22K views
719. Find K-th Smallest Pair Distance | Leetcode HARD | Binary Search Series | LEETCODEcode Explainer · 9:05 · 16K views
Find K-th Smallest Pair Distance | Multiple Approaches | Leetcode 719 | codestorywithMIKcodestorywithMIK · 53:54 · 15K views
Find K-th Smallest Pair Distance | LeetCode 719 | Coders CampCoders Camp · 12:48 · 7K views
LeetCode 719. Find K-th Smallest Pair DistanceErik Gao · 16:44 · 4K views
Find k-th smallest pair Distance | Leetcode hard | Interview QuestionSukeesh V · 14:49 · 3K views
Find K-th Smallest Pair Distance | Leetcode 719Ayushi Sharma · 28:13 · 1K views
719. Find K-th Smallest Pair Distance (Leetcode Hard)Programming Live with Larry · 25:05 · 1K views
leetcode 719 Find K-th Smallest Pair Distance Analysis & ImplementationJessieW · 3:30 · 1K views
Find K-th Smallest Pair Distance (LeetCode 719) (Hard) (3 Approaches) (Binary Search,Sliding Window)CodeWithARB · 35:39 · 886 views
The problem
The distance of a pair of integers a and b is defined as the absolute difference between a and b.
Given an integer array nums and an integer k, return the kth smallest distance among all the pairs nums[i] and nums[j] where 0 <= i < j < nums.length.
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.
Example 2:
Input: nums = [1,1,1], k = 2 Output: 0
Example 3:
Input: nums = [1,6,1], k = 3 Output: 5
Constraints:
n == nums.length2 <= n <= 1040 <= nums[i] <= 1061 <= k <= n * (n - 1) / 2
Approach overview
Problem Overview: You receive an integer array nums and an integer k. Consider the absolute difference between every pair (i, j) where i < j. The task is to return the k-th smallest pair distance among all these differences.
Approach 1: Sort and Use a Min-Heap (O(n log n + k log n) time, O(n) space)
Start by sorting the array so pair distances become easier to manage. For each index i, the smallest distance involving that element is with i + 1. Push these initial pairs into a min-heap keyed by their distance. Each heap pop gives the next smallest distance. After removing a pair (i, j), push the next pair (i, j + 1) if it exists. This works similarly to merging sorted lists, where each row represents distances starting from the same element. Sorting costs O(n log n), and extracting k distances from the heap costs O(k log n). Useful when k is relatively small compared to the total number of pairs.
Approach 2: Binary Search on Distance + Two Pointers (O(n log n + n log W) time, O(1) space)
The key observation: instead of enumerating all pair distances, you can binary search the answer. The smallest possible distance is 0, and the largest is max(nums) - min(nums). After sorting the array, guess a distance mid and count how many pairs have distance ≤ mid. This counting step uses the two pointers technique: move a right pointer forward and advance the left pointer whenever the difference exceeds mid. Each step adds right - left valid pairs.
If the number of pairs ≤ mid is at least k, the k-th distance must be ≤ mid, so shrink the search range. Otherwise increase the distance. This binary search continues until the smallest feasible distance is found. The counting step runs in O(n), and the binary search runs log W iterations where W is the value range.
This approach avoids generating all O(n²) pairs. The array is sorted once using sorting, and every iteration efficiently counts valid pairs.
Recommended for interviews: Binary search on distance combined with two pointers is the expected solution. It demonstrates strong understanding of search space reduction and pair counting techniques. The heap approach proves you can model the problem with priority queues, but interviewers typically look for the binary search insight because it scales better for large arrays.
Approach 1: Approach 1: Sort and Use a Min-Heap
This approach utilizes sorting and a min-heap (or priority queue) to efficiently manage and retrieve the k-th smallest distance. The key steps are:
- Sort the array
nums. This simplifies the process of finding the distances as all distance calculations will involve consecutive elements. - Use a priority queue to dynamically manage the smallest pair distances.
- Iterate through the array to compare all pairs, compute their distances, and manage the dynamic pool of smallest distances using the min-heap.
- Finally, extract the k-th smallest distance from the min-heap.
import heapq
def find_kth_smallest_pair_distance(nums, k):
nums.sort()
pq = []
for i in range(len(nums)-1):
for j in range(i+1, len(nums)):
heapq.heappush(pq, abs(nums[j] - nums[i]))
for _ in range(k-1):
heapq.heappop(pq)
return heapq.heappop(pq)#include <vector>
#include <queue>
#include <algorithm>
int findKthSmallestPairDistance(std::vector<int>& nums, int k) {
std::sort(nums.begin(), nums.end());
std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
for (int i = 0; i < nums.size() - 1; ++i) {
for(int j = i + 1; j < nums.size(); ++j) {
minHeap.push(std::abs(nums[j] - nums[i]));
}
}
for (int i = 0; i < k - 1; ++i) {
minHeap.pop();
}
return minHeap.top();
}First, the array is sorted to enable orderly distance calculations. A min-heap (priority queue) is used to efficiently manage the distances and extract the k-th smallest. After computing and storing distances in the heap, we extract the smallest k elements, finally returning the k-th one.
Time Complexity: O(n^2 log n) due to the double loop and heap operations.
Space Complexity: O(n^2) for storing all possible distances in the heap.
Approach 2: Approach 2: Binary Search on Distance Combined with Two-pointers
This more efficient approach combines binary search with a two-pointer technique. The principal idea is to use binary search over distance values to pinpoint the k-th smallest distance. It involves:
- Sorting the array
nums. - Using binary search for the smallest distance, verifying with two pointers how many distances are less than a given middle, adjusting search space based on the count.
- The two-pointer method efficiently counts how many distances are smaller than the middle of the binary search range at each step.
def find_kth_smallest_pair_distance(nums, k):
nums.sort()
left, right = 0, nums[-1] - nums[0]
def count_pairs(max_dist):
count, j = 0, 0
for i in range(len(nums)):
while j < len(nums) and nums[j] - nums[i] <= max_dist:
j += 1
count += j - i - 1
return count
while left < right:
mid = (left + right) // 2
if count_pairs(mid) < k:
left = mid + 1
else:
right = mid
return leftimport java.util.Arrays;
public class Solution {
private int countPairs(int[] nums, int mid) {
int count = 0, j = 0;
for (int i = 0; i < nums.length; i++) {
while (j < nums.length && nums[j] - nums[i] <= mid) j++;
count += j - i - 1;
}
return count;
}
public int smallestDistancePair(int[] nums, int k) {
Arrays.sort(nums);
int left = 0, right = nums[nums.length - 1] - nums[0];
while (left < right) {
int mid = (left + right) / 2;
if (countPairs(nums, mid) < k) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
}#include <vector>
#include <algorithm>
int countPairs(std::vector<int>& nums, int max_dist) {
int count = 0, j = 0;
for (int i = 0; i < nums.size(); i++) {
while (j < nums.size() && nums[j] - nums[i] <= max_dist) j++;
count += j - i - 1;
}
return count;
}
int findKthSmallestPairDistance(std::vector<int>& nums, int k) {
std::sort(nums.begin(), nums.end());
int left = 0, right = nums.back() - nums.front();
while (left < right) {
int mid = (left + right) / 2;
if (countPairs(nums, mid) < k) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}This solution involves a binary search to determine the smallest possible distance. The associated helper function utilizes a two-pointer technique to count how many pairs have distances less than a proposed distance during the search process. Adjusting the binary search bounds based on this count homes in on the k-th smallest.
Time Complexity: O(n log n + n log(maxDistance))
Space Complexity: O(1) as no additional space beyond fixed variables is used.
Approach 3: Default Approach
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
function smallestDistancePair(nums, k) {
nums.sort((a, b) => a - b);
const n = nums.length;
let left = 0,
right = nums[n - 1] - nums[0];
while (left < right) {
const mid = (left + right) >> 1;
let count = 0,
i = 0;
for (let j = 0; j < n; j++) {
while (nums[j] - nums[i] > mid) {
i++;
}
count += j - i;
}
if (count >= k) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}function smallestDistancePair(nums: number[], k: number): number {
nums.sort((a, b) => a - b);
const n = nums.length;
let left = 0,
right = nums[n - 1] - nums[0];
while (left < right) {
let mid = (left + right) >> 1;
let count = 0,
i = 0;
for (let j = 0; j < n; j++) {
// 索引[i, j]距离nums[j]的距离<=mid
while (nums[j] - nums[i] > mid) {
i++;
}
count += j - i;
}
if (count >= k) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}func smallestDistancePair(nums []int, k int) int {
sort.Ints(nums)
n := len(nums)
left, right := 0, nums[n-1]-nums[0]
count := func(dist int) int {
cnt := 0
for i, v := range nums {
target := v - dist
left, right := 0, i
for left < right {
mid := (left + right) >> 1
if nums[mid] >= target {
right = mid
} else {
left = mid + 1
}
}
cnt += i - left
}
return cnt
}
for left < right {
mid := (left + right) >> 1
if count(mid) >= k {
right = mid
} else {
left = mid + 1
}
}
return left
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Sort and Use a Min-Heap | Time Complexity: O(n^2 log n) due to the double loop and heap operations. |
| Approach 2: Binary Search on Distance Combined with Two-pointers | Time Complexity: O(n log n + n log(maxDistance)) |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sort + Min-Heap | O(n log n + k log n) | O(n) | Good when k is relatively small and you want to generate distances in sorted order |
| Binary Search on Distance + Two Pointers | O(n log n + n log W) | O(1) | Best scalable solution for large arrays; common interview expectation |
Frequently asked questions
Is Find K-th Smallest Pair Distance easy or hard?
The problem is classified as Hard because it requires recognizing a binary-search-on-answer pattern rather than enumerating pairs. Efficient counting with the two-pointer technique is the key insight that reduces the complexity from O(n²) to near O(n log n).
Find K-th Smallest Pair Distance Python/Java solution
Most implementations first sort the array, then apply binary search on the distance. During each step, two pointers count how many pairs have distance less than or equal to the current guess. This approach is concise and efficient in Python, Java, and C++ with O(n log n + n log W) complexity.
How to solve Find K-th Smallest Pair Distance in O(n)?
A strict O(n) solution does not exist because the array must be sorted first. The closest practical complexity is O(n log n + n log W) using binary search on the distance. Sorting enables the two-pointer counting technique that evaluates pair counts in linear time per iteration.
What is the best approach for Find K-th Smallest Pair Distance?
Binary search on the distance combined with a two-pointer counting technique is the most efficient approach. After sorting the array, binary search guesses a distance and counts how many pairs have difference less than or equal to it. The counting step runs in O(n), and the binary search runs log W iterations where W is the value range. Overall complexity is O(n log n + n log W).
Is Find K-th Smallest Pair Distance asked at Google/Amazon/Meta?
This problem is commonly used in interviews at companies that emphasize algorithmic optimization such as Google, Amazon, and Meta. It tests understanding of binary search on the answer space, two-pointer techniques, and efficient pair counting.
What data structure is used in Find K-th Smallest Pair Distance?
Two main structures appear in solutions. A min-heap (priority queue) can generate pair distances in sorted order. The optimal approach mainly relies on a sorted array and the two-pointer technique, combined with binary search over the possible distance range.
What is the time complexity of Find K-th Smallest Pair Distance?
The optimal algorithm runs in O(n log n + n log W) time. Sorting the array takes O(n log n), and each binary search step counts valid pairs in O(n) using two pointers. W represents the range between the maximum and minimum numbers in the array.