Watch 10 video solutions for Minimize Max Distance to Gas Station, a hard level problem involving Array, Binary Search. This walkthrough by code_report has 10,241 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an integer array stations that represents the positions of the gas stations on the x-axis. You are also given an integer k.
You should add k new gas stations. You can add the stations anywhere on the x-axis, and not necessarily on an integer position.
Let penalty() be the maximum distance between adjacent gas stations after adding the k new stations.
Return the smallest possible value of penalty(). Answers within 10-6 of the actual answer will be accepted.
Example 1:
Input: stations = [1,2,3,4,5,6,7,8,9,10], k = 9 Output: 0.50000
Example 2:
Input: stations = [23,24,36,39,46,56,57,65,84,98], k = 1 Output: 14.00000
Constraints:
10 <= stations.length <= 20000 <= stations[i] <= 108stations is sorted in a strictly increasing order.1 <= k <= 106Problem 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.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Incremental Placement | O(kn) | O(n) | Conceptual understanding of reducing the largest gap; works only when k is small |
| Max Heap Simulation | O((n + k) log n) | O(n) | Efficient improvement over brute force when k is moderate |
| Binary Search on Answer | O(n log W) | O(1) | Optimal approach for large k and interview settings |