In the wild · git bisect: To find the commit that broke a build, git halves the range of commits on every test, so even 1,000 commits take about 10 checks.

About this problem

Cut a sorted search space in half each step. Also used on answer ranges, not only arrays.

Read the full statement and examples on LeetCode, try it for 20–30 minutes, then come back for the walkthrough.

Examples

Full statement on LeetCode ↗

Example 1
Input
position = [1, 2, 3, 4, 7]m = 3
Output
3
Example 2
Input
position = [1, 2]m = 2
Output
1
Example 3
Input
position = [1, 5, 9, 13]m = 4
Output
4

Code it here

Tab indents · ⌘/Ctrl+Enter runs · Esc leaves the editor

Step 6

Get it accepted

All test cases pass

Step 7

Review it so it sticks

Re-solve from memory after

The step that matters most: without reviews most of a solved problem fades within weeks. Three short re-solves, each just as you start to forget, are what make it yours.

Your notes

Three lines in your own words. They come back with this problem's reviews, so you can check yourself after recalling the solution.

Solve it yourself before you look

Reading the solution first feels like progress, but it makes the next similar problem — and the interview version — much harder, because you skipped the part where you figure it out. Give it an honest 20–30 minutes. Stuck? Re-read the pattern, watch the concept video, or try the brute force first.

Hidden: optimal solution

Stuck? One hint at a time.

or find it yourself with the pattern finder

Solution code

Optimal solution

Time O(n log n + n log(range))Space O(1) beyond the sort

Sort the positions and on the answer, the smallest gap. For a gap g, place balls greedily from the left whenever the next position is at least g away; if all m fit, try a bigger gap.

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()

        def fits(gap: int) -> bool:
            placed, last = 1, position[0]
            for p in position[1:]:
                if p - last >= gap:
                    placed += 1
                    last = p
            return placed >= m

        lo, hi = 1, position[-1] - position[0]
        while lo < hi:
            mid = (lo + hi + 1) // 2   # round up: we keep mid when it fits
            if fits(mid):
                lo = mid
            else:
                hi = mid - 1
        return lo

Reference solution, tested in Python, Java and C++.

Other ways to solve it

Thought of another approach (slower, or cleverer)? Code it here: the same tests check any approach.
Community solutions on LeetCode ↗ for many more versions, in many languages. Read them after you've solved it.

Srujan's notes aren't here yet. When he solves this one in his journal, his own writeup and solutions show up on this page too.

Examples

Example 1

Example 2

Example 3

Code it here

Your notes

Solve it yourself before you look

Solution code