Find K-th Smallest Pair Distance - Solution & Explanation
Problem Statement
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.
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.
Complexity
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.
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.
Complexity
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
Code
Python
Java
C++
Go
TypeScript
JavaScript
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 | — |
Detailed 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 |
Video Solution
Find K-th Smallest Pair Distance - Leetcode 719 - Python • NeetCodeIO • 22,082 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Find K-th Smallest Pair Distance easy or hard?
Find K-th Smallest Pair Distance Python/Java solution
How to solve Find K-th Smallest Pair Distance in O(n)?
What is the best approach for Find K-th Smallest Pair Distance?
Is Find K-th Smallest Pair Distance asked at Google/Amazon/Meta?
What data structure is used in Find K-th Smallest Pair Distance?
What is the time complexity of Find K-th Smallest Pair Distance?
Ready to solve this problem?
Practice Find K-th Smallest Pair Distance with our built-in code editor and test cases.
Practice on FleetCode