K-th Smallest Pair Gap

HardBinary Search

Problem

A lab has nums, the heights of its specimens. For every pair of different specimens (i, j) with i < j, the pair gap is |nums[i] - nums[j]|.

Return the k-th smallest pair gap (1-based) among all n · (n - 1) / 2 pairs.

Example 1

Input:
nums = [1, 6, 3, 10], k = 3
Output:
4

The six gaps are 5, 2, 9, 3, 4, 7; sorted: 2, 3, 4, 5, 7, 9. The third is 4.

Example 2

Input:
nums = [5, 5, 5], k = 2
Output:
0

Example 3

Input:
nums = [1, 10], k = 1
Output:
9

Constraints

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

Hint

Show the first hint

There can be about 5 · 10^7 pairs, too many to list. Can you count how many pairs have gap ≤ d instead?

Walkthrough

How to approach it

01Clarify before coding

  • Do equal heights at different positions form a pair? Yes, with gap 0.
  • Is k 1-based? Yes.
  • Can I sort the array? Yes: gaps do not depend on order.

02Brute force

Compute every pair gap, sort them and return element k - 1 (or use a heap of size k).

Cost: O(n² log n) time and O(n²) memory: 5 · 10^7 gaps for n = 10^4.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.