Free Binary search lessonsBinary search · Stage 2 · Search on the answer · Step 4

The k-th smallest gap

Find the k-th smallest difference between pairs without listing the pairs, by searching the difference and counting pairs under it. About 16 minutes.

Count instead of list

Given some numbers, the gaps between every pair, sorted, make a long list. You want its k-th entry. The list has about n squared over 2 entries, so you can't build it.

But you can ask a cheaper question: for a gap d, how many pairs have a gap of at most d? That count only grows as d grows. So the k-th smallest gap is the smallest d whose count reaches k, and you can find it by halving the range of possible gaps.

Count at most d: grows as d grows.

Answer: the smallest d whose count reaches k.

In code

nums.sort()
low, high = 0, nums[-1] - nums[0]
while low < high:
    mid = (low + high) // 2
    if count_at_most(mid) >= k:
        high = mid
    else:
        low = mid + 1
return low

Numbers 1, 3, 5, 9. Gaps sorted: 2, 2, 4, 4, 6, 8. Find the 4th smallest.

123

low

high

middle

pairs at most middle

The gap is between 0 and 8. Try 4: four pairs (2, 2, 4, 4) have a gap of at most 4. That reaches k = 4, so keep 4 and look lower.

Move 1 of 3

Counting with two pointers

Sort the numbers. For each right position, the numbers within d of it form a stretch ending at it, starting at some left position. As right moves up, left only moves up too, never back.

So one pass counts everything: for each right, move left forward while the gap is more than d, then add right minus left, the number of earlier values that pair with it.

Left never goes back: so one pass is enough.

Add right minus left: pairs ending at this right.

In code

def count_at_most(d):
    total, left = 0, 0
    for right in range(len(nums)):
        while nums[right] - nums[left] > d:
            left += 1
        total += right - left
    return total

Quick check

For a gap d, you count 6 pairs with a gap at most d and you need the 9th smallest. What next?

ALook at bigger gaps, since 6 is fewer than 9
BLook at smaller gaps
CStop: d is the answer

Show the answer

Look at bigger gaps, since 6 is fewer than 9. The 9th smallest gap is larger than d, because only 6 pairs fit within it.

Your problem

K-th smallest gap

nums is a list of whole numbers. The gap of a pair of positions i < j is the absolute difference between nums[i] and nums[j]. Return the k-th smallest gap over all pairs, counting equal gaps separately. For example, if the gaps are 1, 1 and 3, the 2nd smallest is 1.

Example

nums = [1, 3, 5, 9], k = 4 → 4

2 ≤ length ≤ 20,000 · 0 ≤ value ≤ 1,000,000 · 1 ≤ k ≤ length × (length − 1) / 2

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.