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) / 2Problem 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.
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:
nums. This simplifies the process of finding the distances as all distance calculations will involve consecutive elements.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.
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:
nums.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.
Python
Java
C++
Go
TypeScript
JavaScript
| 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 | — |
| 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 |
Find K-th Smallest Pair Distance - Leetcode 719 - Python • NeetCodeIO • 21,300 views views
Watch 9 more video solutions →Practice Find K-th Smallest Pair Distance with our built-in code editor and test cases.
Practice on FleetCode