Skip to main content

719. Find K-th Smallest Pair Distance

hard

Among all pairs (i, j) with i < j, find the kth smallest absolute difference. A textbook 'binary-search on the answer' problem layered with a two-pointer counting predicate.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

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.

Constraints

  • n == nums.length
  • 2 <= n <= 10^4
  • 0 <= nums[i] <= 10^6
  • 1 <= k <= n * (n - 1) / 2

Examples

Example 1

Input
nums = [1,3,1], k = 1
Output
0

Explanation: Pair distances: (1,3)=2, (1,1)=0, (3,1)=2. Sorted: [0,2,2]. The 1st smallest is 0.

Example 2

Input
nums = [1,1,1], k = 2
Output
0

Example 3

Input
nums = [1,6,1], k = 3
Output
5

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Brute force: enumerate all O(n^2) pair distances, sort, return index k-1. O(n^2 log n) — too slow for n=10^4.

Hint 2

Sort nums first. Now the answer lies in [0, nums[n-1] - nums[0]]. Binary-search the answer.

Hint 3

Predicate: count(d) = number of pairs with distance <= d. count is monotonically non-decreasing in d.

Hint 4

Compute count(d) in O(n) via a two-pointer sliding window over the sorted array. Find the smallest d where count(d) >= k.

Solution approach

Reveal approach

Sort nums in ascending order. The answer lies in the range [0, nums[n-1] - nums[0]]. Binary-search the smallest distance d such that at least k pairs have distance <= d. Counting predicate count(d): use a two-pointer sliding window. Walk right pointer r from 0 to n-1; advance left pointer l while nums[r] - nums[l] > d. Then r - l pairs ending at index r have distance <= d. Sum these counts as you go — total O(n). Binary search: lo = 0, hi = nums[n-1] - nums[0]. While lo < hi, mid = lo + (hi - lo) / 2; if count(mid) >= k, hi = mid; else lo = mid + 1. Return lo. Total time: O(n log n) for sort + O(n log W) for the binary search where W = max distance. Space: O(1) extra (or O(log n) for sort). The two layers — binary-search-on-answer plus a sliding-window predicate — are the canonical pattern for this problem family.

Complexity

Time
O(n log n + n log W) where W = max distance
Space
O(1) extra

Related patterns

  • binary-search
  • binary-search-on-answer
  • two-pointers
  • sliding-window

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Google
  • Amazon
  • Meta
  • Microsoft

Practice these live with InterviewChamp.AI

Drill Find K-th Smallest Pair Distance and Binary Search problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →