← DSA Atlas
Dedicated problem page · #774

Minimize Max Distance to Gas Station

HardBinary SearchBinary search on a real-valued answerBinary search on the answer (parametric search)
Solve on LeetCode ↗
774
HardBinary SearchBinary search on the answer (parametric search)Binary search on a real-valued answer

Minimize Max Distance to Gas Station

You are given a sorted array stations of positions of existing gas stations along a horizontal line and an integer k. You may add exactly k new gas stations anywhere (positions need not be integers). Let penalty be the maximum distance between any two adjacent gas stations after the additions. Return the smallest possible penalty. Answers within 1e-6 of the true value are accepted.

Open official problem prompt ↗
In plain English

Find the smallest possible maximum spacing between adjacent gas stations after inserting k new ones.

Picture it like this

You are placing rest stops on a highway. Given a budget of k new stops, you want the longest stretch without a stop to be as short as possible. You guess a maximum acceptable stretch, check how many stops that guess demands, and tighten the guess.

Example
Input
stations = [1,2,3,4,5,6,7,8,9,10], k = 9
Output
0.50000
Why
There are nine unit gaps; placing one new station in each gap halves every gap to 0.5, and no smaller maximum is achievable with only nine stations.
Constraints
10 <= stations.length <= 20000 <= stations[i] <= 10^8stations is sorted in strictly increasing order1 <= k <= 10^6Answers within 10^-6 of the correct value are accepted
Pattern lesson

See the pattern, then code

Binary search on a real-valued answer
Recognition clue

You are minimizing a maximum, the answer is a continuous value, and a candidate distance is easy to test for feasibility - the classic signature of binary search on the answer.

↗
Binary Search

Sorted data or a monotonic true/false condition over a possible answer.. If a maximum gap of d is achievable, then any larger d is also achievable, so feasibility is monotonic. For a candidate d, a gap of length g needs floor(g/d) extra stations to break it into pieces no longer than d; summing that over all gaps tells you whether k stations suffice.

New words, made simpleKnow these before the algorithm
Binary search on the answer
Searching over possible output values (here a distance) rather than over array indices, using a feasibility test to steer the search.
Monotone predicate
A yes/no test that, once true, stays true as the parameter grows - what makes the search valid.
Feasibility check
Given candidate distance d, whether k or fewer stations can force every gap to at most d.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Greedy largest-gap heap

Intuitive but k can be up to 10^6, and greedily splitting the largest gap does not guarantee the global optimum for the max spacing.

Repeatedly split the currently largest sub-gap by inserting a station.

Time O(k log n)Space O(n)
Best choiceBinary search on distance

Turns an optimization into repeated feasibility checks and hits the 1e-6 tolerance efficiently.

Guess a maximum distance d and count int(gap/d) stations needed across all gaps.

Time O(n log(W/eps))Space O(1)
The rule we keep true

Invariant

hi is always a feasible maximum distance (achievable with <= k stations) while lo is always infeasible, so the true answer lies in (lo, hi].

Why this is correct

Reasoning

For a fixed candidate d, a gap of length g must be divided into pieces of length at most d, which requires ceil(g/d)-1 = floor(g/d) new stations (for non-exact ratios). Summing these across gaps gives the minimum stations to guarantee spacing d, and this sum only decreases as d grows - a monotone predicate. Binary search over d therefore converges on the boundary between infeasible and feasible, which is the minimum achievable maximum distance, to within the requested tolerance.

The algorithm in three movesSay these aloud before coding
1Set lo=0 and hi to the largest existing gap (or span)

hi = 9.0 (max span); lo = 0.0

2Pick mid = (lo+hi)/2 as a candidate maximum distance

test d=0.5: each gap needs int(1/0.5)=... just above 0.5 needs 1 each -> total 9 <= 9 feasible

3Count stations needed: sum of int(gap/mid) over all adjacent gaps

binary search converges hi -> 0.5

4If the count is <= k, mid is feasible so shrink hi = mid; else lo = mid

5Stop when hi - lo <= 1e-6 and return hi

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
10
21
32
43
54
65
76
87
98
109
1 · Readstations span 1..10
2 · AskWhat range holds the answer?
3 · Update statelo=0.0, hi=9.0
4 · ResultInterval (0, 9] brackets the optimum
Key takeaway

Ten evenly spaced stations with nine unit gaps; nine inserted stations halve each gap to 0.5.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3-7Feasibility test

    For candidate distance d, int(gap/d) counts how many extra stations a gap needs; the total decides whether k suffice.

  2. 2
    Lines 8Bound the answer

    The answer is at least 0 and at most the full span between first and last stations.

  3. 3
    Lines 9-14Floating binary search

    Shrink toward the smallest feasible distance, stopping once the window is tighter than the 1e-6 tolerance.

  4. 4
    Lines 15Return the boundary

    hi is the smallest distance shown feasible, which is the minimized maximum spacing.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • k far larger than needed (answer approaches 0)
  • All gaps equal (each needs the same split count)
  • One dominant huge gap that consumes most stations
  • Very small tolerance requiring many iterations
!

Common beginner mistakes

  • Terminating on exact equality with floats instead of a tolerance, risking non-termination
  • Using lo = mid+1 / hi = mid-1 as with integer search - the domain is continuous, so use lo = mid / hi = mid
  • Setting hi too small (e.g. average gap) and excluding the true answer
  • Off-by-one in the station count formula: floor(g/d) is stations added, not pieces created
Check your understanding

Why can we binary search on the distance at all - what property must the feasibility test have?

More in Binary Search

#33Search in Rotated Sorted ArrayBinary search on a rotated array#153Find Minimum in Rotated Sorted ArrayBinary search for the rotation point#875Koko Eating BananasBinary search on the answer#4Median of Two Sorted ArraysBinary search on the partition#34Find First and Last Position of ElementLower-bound binary search on both ends#35Search Insert PositionLower-bound binary search