Minimize Max Distance to Gas Station solution and explanation
Google
9 more videos on this problem
LeetCode 774. Minimize Max Distance to Gas StationHappy Coding · 21:44 · 7K views
Leetcode 774. Minimize Max Distance to Gas StationAlgorithms for Big Bucks · 9:01 · 958 views
774. Minimize Max Distance to Gas Station (Leetcode Hard)Programming Live with Larry · 23:18 · 855 views
774. Minimize Max Distance to Gas Station - Week 2/5 Leetcode October ChallengeProgramming Live with Larry · 11:34 · 590 views
Day 83/90 |🔥LeetCode 774 - Minimize Max Distance to Gas Station Using Binary Search on Answer 🚀#9CTO Bhaiya · 50:17 · 573 views
Leetcode 774. Minimize Max Distance to Gas Station (binary search a value)LetsCode · 19:16 · 440 views
Minimize Max Distance to Gas Station - LeetCode Hard - Binary Search on AnswerCodeLucky · 4:29 · 169 views
Minimize Max Distance to Gas Station ⛽ | LeetCode 774 (Binary Search Explained) #cpp #interviewaksdev · 7:30 · 15 views
LeetCode 774: Minimize Max Distance to Gas StationAlitaCode · 30:59 · 13 views
Minimize Max Distance Gas Station ⛽ | LeetCode 774 Easy Explanation (Hindi) #cpp #interview #dsaaksdev · 7:48 · 10 views
The problem
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] <= 108stationsis sorted in a strictly increasing order.1 <= k <= 106
Approach overview
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.
Solution
class Solution:
def minmaxGasDist(self, stations: List[int], k: int) -> float:
def check(x):
return sum(int((b - a) / x) for a, b in pairwise(stations)) <= k
left, right = 0, 1e8
while right - left > 1e-6:
mid = (left + right) / 2
if check(mid):
right = mid
else:
left = mid
return leftclass Solution {
public double minmaxGasDist(int[] stations, int k) {
double left = 0, right = 1e8;
while (right - left > 1e-6) {
double mid = (left + right) / 2.0;
if (check(mid, stations, k)) {
right = mid;
} else {
left = mid;
}
}
return left;
}
private boolean check(double x, int[] stations, int k) {
int s = 0;
for (int i = 0; i < stations.length - 1; ++i) {
s += (int) ((stations[i + 1] - stations[i]) / x);
}
return s <= k;
}
}class Solution {
public:
double minmaxGasDist(vector<int>& stations, int k) {
double left = 0, right = 1e8;
auto check = [&](double x) {
int s = 0;
for (int i = 0; i < stations.size() - 1; ++i) {
s += (int) ((stations[i + 1] - stations[i]) / x);
}
return s <= k;
};
while (right - left > 1e-6) {
double mid = (left + right) / 2.0;
if (check(mid)) {
right = mid;
} else {
left = mid;
}
}
return left;
}
};func minmaxGasDist(stations []int, k int) float64 {
check := func(x float64) bool {
s := 0
for i, v := range stations[:len(stations)-1] {
s += int(float64(stations[i+1]-v) / x)
}
return s <= k
}
var left, right float64 = 0, 1e8
for right-left > 1e-6 {
mid := (left + right) / 2.0
if check(mid) {
right = mid
} else {
left = mid
}
}
return left
}Complexity analysis
| 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 |
Frequently asked questions
Is Minimize Max Distance to Gas Station easy or hard?
LeetCode classifies this problem as Hard because it requires recognizing the binary-search-on-answer pattern and handling floating-point precision correctly. The feasibility logic itself is simple, but identifying the monotonic property is the key challenge.
Minimize Max Distance to Gas Station Python/Java solution
Most implementations follow the same pattern: binary search on the distance range and compute how many stations are required for each guess. The code works similarly across Python, Java, C++, and Go because it relies only on array iteration and floating-point binary search.
How to solve Minimize Max Distance to Gas Station in O(n log W)?
Use binary search over the maximum allowed distance between adjacent stations. For each candidate distance d, iterate through the array and calculate required += floor((stations[i+1] - stations[i]) / d). If the total required stations is ≤ k, the distance is feasible and you shrink the search range. Continue until the range converges to the required precision.
What is the best approach for Minimize Max Distance to Gas Station?
Binary search on the answer combined with a greedy feasibility check is the optimal approach. You guess a maximum allowed distance d and compute how many additional stations are required so every gap becomes ≤ d. If the required stations exceed k, the distance is too small. This runs in O(n log W) time where W is the largest gap between stations.
Is Minimize Max Distance to Gas Station asked at Google/Amazon/Meta?
This problem reflects a common interview pattern used by companies like Google, Amazon, and Meta: binary search on the answer with a feasibility check. Variations of minimizing the maximum value in a continuous range appear frequently in system optimization and load balancing interview questions.
What data structure is used in Minimize Max Distance to Gas Station?
The optimal solution mainly uses arrays and binary search. A feasibility check iterates through the array of station positions and calculates required insertions. Some alternative solutions also use a max heap (priority queue) to repeatedly split the largest gap.
What is the time complexity of Minimize Max Distance to Gas Station?
The optimal binary search solution runs in O(n log W) time and O(1) space. Each binary search step scans all station gaps to compute how many stations are needed for a candidate distance. W represents the maximum distance between two existing stations.