Minimize Max Distance to Gas Station - Solution & Explanation

Problem Overview: You are given sorted gas station positions along a road and allowed to add k new stations. The goal is to minimize the maximum distance between any two adjacent stations after placement. The result is a floating-point distance.

Approach 1: Brute Force Incremental Placement (O(kn), O(n) space)

Track the current gaps between adjacent stations and repeatedly place a station inside the largest gap. After inserting a station in a segment, that segment splits into smaller equal segments. You recompute the maximum segment length each time. This works because reducing the largest gap always improves the maximum distance. The downside is performance: each of the k insertions scans all n gaps, leading to O(kn) time. The idea builds intuition but does not scale for large k.

Approach 2: Max Heap Simulation (O((n + k) log n), O(n) space)

Store each gap in a max heap keyed by its current largest segment length. Every time you add a station to the largest gap, increase the split count for that segment and recompute its effective distance: gap / (splits + 1). Push the updated segment back into the heap. This ensures you always reduce the currently worst gap. Compared with brute force, the heap avoids scanning the entire array each step, but the algorithm still performs k operations. When k is very large (up to 10^6), the approach becomes too slow.

Approach 3: Binary Search on Maximum Distance (O(n log W), O(1) space)

This is the optimal approach and relies on binary search over the answer. Instead of deciding where to place stations directly, guess the maximum allowed distance d between adjacent stations. Then check if it is feasible. For each existing gap gap = stations[i+1] - stations[i], compute how many stations are required to ensure every segment is ≤ d: required += floor(gap / d). If the total required stations is ≤ k, the distance is feasible. Otherwise it is too small.

The search space ranges from 0 to the largest existing gap. Repeatedly narrow the range until the difference between bounds is within a small precision (for example 1e-6). Each feasibility check scans the array once, giving O(n) work per iteration. With ~60 binary search iterations for floating precision, the total complexity is O(n log W), where W is the maximum gap.

This technique is common when minimizing the maximum value under constraints. It converts a placement optimization problem into a monotonic decision problem. Problems using sorted arrays with continuous answers frequently use this pattern.

Recommended for interviews: The binary search on answer approach. Interviewers expect you to recognize the monotonic property: if distance d is feasible, any larger distance is also feasible. Mentioning the brute force or heap idea first shows understanding of the optimization goal, but implementing the binary search feasibility check demonstrates strong algorithmic thinking.