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.

Description Hints 1 Solution Video 25:35

719. Find K-th Smallest Pair Distance

Hard46.4% acceptance5 companies

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 k^th 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 1^st 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.length
2 <= n <= 10⁴
0 <= nums[i] <= 10⁶
1 <= k <= n * (n - 1) / 2

Asked at 5 companies

Uber

Google Amazon Bloomberg Microsoft

Topics

Hints open one at a time

Hint 1

Binary search for the answer. How can you check how many pairs have distance <= X?

25:35

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution