BS on Answer — Minimize Max Distance to Gas Station

↗ LeetCode: Minimize Max Distance to Gas Station · Hard · pattern chapter →

Asked atGoogleAmazon

Given sorted station positions and integer k, add k new stations to minimize the max distance between adjacent stations. Return that distance (real number).

Example — stations=[1,2,3,4,5,6,7,8,9,10], k=9 → 0.5

Constraints — 10 ≤ stations.length ≤ 2000; 0 ≤ stations[i] ≤ 10⁸.

Progressive Hints

Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.

---

⏱️Interview timer00:00

Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.

Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.

Approach 1 — Priority queue (greedy)

Track each gap's current "sub-gap size after splits"; repeatedly split the largest. O(k log n).

Approach 2 — Binary search on real-number answer

Insight. feasible(D) = "can we place ≤ k stations so every gap ≤ D?" — for each existing gap g, we need ⌈g/D⌉ - 1 splits (i.e. floor(g/D) new stations). Total ≤ k.

Trap. Real BS: use a small epsilon or a fixed number of iterations to converge.

java

double minmaxGasDist(int[] s, int k) {
    double lo = 0, hi = s[s.length - 1] - s[0];
    while (hi - lo > 1e-6) {
        double mid = (lo + hi) / 2;
        int count = 0;
        for (int i = 1; i < s.length; i++) count += (int) ((s[i] - s[i - 1]) / mid);
        if (count > k) lo = mid;                                // need more allowed → increase D
        else            hi = mid;
    }
    return lo;
}

Execution Trace

Priority queue (greedy)

Step 1 / 3Initialize scan.

Complexity — Time O(n log(hi/eps)) ≈ O(n · 30); Space O(1).

Try it yourself

Complexity summary

Approach	Time	Space
Max-heap greedy	O(k log n)	O(n)
Real-number BS	O(n · log(hi/eps))	O(1)

When to use which

"Minimize max after k operations" → BS on real-valued answer.
Discrete answer → integer BS.
Precision → iterate until hi - lo < 1e-6.

✨AI Study CompanionBeta

Was this page helpful?

BS on Answer — Minimize Max Distance to Gas Station ​

Approach 1 — Priority queue (greedy) ​

Approach 2 — Binary search on real-number answer ​

Try it yourself ​

Complexity summary ​

When to use which ​

Related problems ​