Minimize Max Distance to Gas Station

Gas stations already stand on a horizontal number line at positions arr[0] < arr[1] < ... < arr[n-1]. You are given k more stations to build, and you may place them anywhere on the line — fractional positions are allowed.

After you build them, let d be the maximum distance between two adjacent stations. Your job is to place the k new stations so that d is as small as possible.

Return the smallest possible value of d. Answers are checked to 6 decimal places.

Note: arr is strictly increasing — every adjacent pair already defines a positive gap.

Hints

· Stuck? Reveal one nudge at a time.

Adding a station only helps if it splits the current longest gap — and inside any single gap, evenly spaced stations are always best.

Do not decide where the stations go. Guess a distance d and ask instead: how many stations would I need so that no gap exceeds d? A gap of length g needs ceil(g / d) - 1 of them.

That count only grows as d shrinks — feasibility is monotonic. Binary search on d itself over the real number line, stopping once the search window drops below 1e-6 (about 100 halvings).

Common doubts

Yes. Positions are real numbers, which is why the answer is a decimal like 4.666667 rather than an integer.

All four gaps are already length 1. Two new stations can shrink two of the gaps, but the other two remain at length 1 — the maximum does not move.

Either loop until hi - lo drops below the required precision (use 1e-7 here, tighter than the 1e-6 that is checked), or simply run a fixed 100 iterations — each halving doubles the precision, so 100 is far more than enough.

No stations get added, so the answer is the largest existing gap — a good sanity check for your feasibility function.

Interview follow-ups

· What an interviewer asks next.

Yes — after the binary search finds d, walk each gap g and drop ceil(g / d) - 1 stations evenly spaced inside it.

The same feasibility check works — replace the station count per gap with its cost and binary search on d unchanged. Monotonicity is all the search needs.

Aggressive Cows (maximize the minimum spacing), Split Array Largest Sum, and Koko Eating Bananas — the whole minimize-the-maximum / maximize-the-minimum family shares this exact skeleton.

Fun facts

The technique here is sometimes called parametric search: turn an optimization problem into a family of yes/no questions, then binary search the parameter.
Because the answer is a real number, the binary search never lands on it exactly — it corners the answer inside an interval smaller than the precision anyone cares about. Seasoned contestants just run a fixed 100 halvings and stop worrying.
The same math places water tables along a marathon route and cell towers along a highway: minimize the worst dry stretch, not the average one.

Asked at

GoogleAmazonUberMicrosoftFlipkart

Frequently Sometimes Occasionally

Example 1

Input: arr = [1, 2, 3, 4, 5], k = 2
Output: 1.000000
Every gap is already exactly 1. Two new stations can split two of the four gaps, but the other two stay at length 1 — the maximum cannot drop below 1.

Example 2

Input: arr = [3, 6, 12, 19, 33], k = 3
Output: 6.000000
Put 2 stations in the biggest gap (14, between 19 and 33) to cut it into pieces of about 4.67, and 1 station in the gap of 7 (between 12 and 19) to make pieces of 3.5. The largest remaining gap is 6 (between 6 and 12).

Constraints

- 1 <= arr.size() <= 10^5 - 0 <= arr[i] <= 10^6 - 0 <= k <= 10^5 - arr is strictly increasing

A hard problem with a beautiful reversal at its core: placing stations optimally feels impossible to construct directly — so we stop constructing and start guessing the answer and checking it. The arc: a hands-on greedy, a heap upgrade, and finally a binary search over the real number line.

Prerequisites

Before you start

· Concepts used directly in the solution.

Binary search on the answer. Searching candidate answers instead of array indices — the move that works whenever a guess is easy to verify.

Greedy exchange argument. Why splitting the current largest gap is never wrong — it justifies the brute force and the heap approach.

Max-heap / priority queue. Repeatedly extracting the current worst item in log time powers the middle approach.

Floating-point binary search. The answer is a real number, so the search stops on window size or a fixed iteration count — never on lo greater than hi.

Understand the problem

In one line: choose real (fractional allowed) positions for k new stations so that the largest distance between adjacent stations is minimized, and report that distance to 6 decimal places.

Worked example — arr = [3, 6, 12, 19, 33], k = 3

stations:   3    6       12        19                  33
gaps:         3      6        7             14

2 stations into the 14  →  3 pieces of 14/3 ≈ 4.67
1 station  into the 7   →  2 pieces of 3.5
pieces now: 3, 6, 3.5, 4.67…   largest = 6   ← answer 6.000000

Clarifying questions

A few sharp questions before coding show you think in contracts, not just code.

Questions to ask first

· Signals seniority before you write a line of code.

Input validity

“Is arr strictly increasing, with no duplicate positions?”

Yes — every adjacent pair defines a positive gap, so a zero-length gap never appears in the math.

“Can the new stations sit at fractional positions?”

Yes — that is exactly why the answer is a real number like 4.666667 instead of an integer.

Edge cases

“What if k is 0?”

No stations to add — the answer is simply the largest existing gap.

“What if there is only one station?”

No adjacent pairs exist, so the maximum gap is 0 regardless of where the new stations go.

Constraints and scale

“How large can n and k get?”

Both up to 10^5 — an O(n · k) greedy is 10^10 steps and times out; we need the heap or the binary search.

“How precise must the answer be?”

Six decimal places — a binary search window must shrink below 1e-6, so plan on roughly 100 halvings.

The ideal opening — say it like this

Before I code, let me confirm: the positions are strictly increasing, and the k new stations may go at any real position, correct?

If k is 0 the answer is just the largest existing gap — I will make sure that case falls out naturally.

Since the answer is a real number to six decimals, my instinct is to binary search on the answer itself rather than on station positions.

Key observations

1Aha

Inside one gap, even spacing is unbeatable

If a gap of length g receives m - 1 new stations, the best possible outcome is m equal pieces of g / m — any uneven layout leaves some piece strictly longer. So the search is never about positions, only about how many stations each gap gets.

2Aha

Checking a guess is easy even though constructing is hard

Flip the question. Instead of where do the stations go?, ask: if no gap may exceed d, how many stations must I add? Each gap g needs ceil(g / d) - 1 of them — computed independently, in one pass.

guess d = 5 on a gap of 14:
ceil(14 / 5) = 3 pieces  →  2 stations, each piece 14/3 ≈ 4.67 ≤ 5 ✓

3Aha

Feasibility is monotonic — binary search a real number

If d is achievable, every larger d is too. That clean yes/no boundary is exactly what binary search finds — even over the continuous number line. Halve the window [lo, hi] about 100 times and it collapses far below the required 10^-6 precision.

Brute force vs optimal

	Brute force	Max-heap	Binary search
Time	O(n · k)	O((n + k) log n)	O(n log(W/ε))
Space	O(n)	O(n)	O(n)

Here W is the largest gap (up to 10^6) and ε = 10^-6 is the precision — about 50–100 feasibility checks in total. The full, runnable code for each approach lives in the Approaches selector below.

Summary

Key takeaway

When the best answer is hard to construct but easy to verify, binary search the answer space — even when it is continuous. A monotonic feasibility check is the signature of the whole minimize-the-maximum family.

lo = 0, hi = largest gap
repeat 100 times:
    mid = (lo + hi) / 2
    if stations needed so no gap exceeds mid ≤ k:  hi = mid
    else:                                          lo = mid
return hi