Spread Picks Across Ranges

Medium

You get an array starts of n numbers and a number width. Together they describe n ranges: range i is [starts[i], starts[i] + width], ends included. Pick one integer from every range. The quality of your picks is the smallest distance (absolute difference) between any two picked numbers. Return the largest quality you can achieve.

Example 1

starts=[1, 4, 9], width=3 → 5

The ranges are [1, 4], [4, 7] and [9, 12]. Pick 1, 6 and 11: neighbours are 5 apart. You cannot do better: the first and third picks must fit between 1 and 12, and two gaps of 6 would need 12.

Example 2

starts=[5, 5], width=0 → 0

Both ranges are the single point 5, so the picks are 5 and 5, at distance 0.

Constraints

2 ≤ len(starts) ≤ 10⁵
0 ≤ starts[i] ≤ 10⁹
0 ≤ width ≤ 10⁹

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Array Binary Search Sorting

Similar problems

Stick Triples That Form a Triangle Medium Best-Paid Gig for Each Worker Medium Prices That Fade With Each Sale Medium Even Out With Increments Medium Rug Over Painted Stretches Medium

Input

starts=[1, 4, 9], width=3

Expected

Run checks the first 3 tests in your browser. Submit checks all 102 tests on the server, hidden ones included.