K-th Smallest Gap

HardTwo Pointers

Problem

A sensor network reports positions nums along a straight road. For every pair of sensors at different indices i < j, the gap is |nums[i] - nums[j]|.

Among all n·(n-1)/2 gaps, return the k-th smallest (1-indexed, counting duplicates).

Example 1

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

The gaps sorted are [0, 2, 2, 3, 5, 5]; the third is 2.

Example 2

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

Constraints

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

Hint

Show the first hint

Listing all gaps is O(n²) memory and time. Instead, can you count how many gaps are ≤ some value d?

Walkthrough

How to approach it

01Clarify before coding

  • Is k 1-indexed and do duplicates count? Yes to both.
  • Can positions repeat? Yes, giving zero gaps.
  • How large can n·(n-1)/2 be? About 5·10^7, too many to list.

02Brute force

Compute all gaps, sort them and pick the k-th.

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.