Minimize Max Distance to Gas Station
Minimize Max Distance to Gas Station is a hard binary search problem solved with the binary search on answer space pattern.
The best approach, optimal (binary search on the answer), runs in O(n log(W / ε)) time and O(1) space.
Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (greedy, linear scan per station) up.
Problem
Gas stations stand on a straight road at the coordinates in the sorted array stations. You may build exactly k new stations, at any real-valued coordinates (not necessarily integers).
After building, look at the distance between every pair of neighbouring stations and take the largest one. Place the new stations so that this largest distance is as small as possible, and return it.
Examples
Example 1
- Input
stations = [0, 4, 10], k = 2- Output
3.00000- Why
- Put one new station at 7 (splitting the gap of 6 into 3 + 3) and one at 2 (splitting the gap of 4 into 2 + 2). The largest gap is now 3.
Example 2
- Input
stations = [3, 8, 9, 20], k = 1- Output
5.50000- Why
- The only useful move is to halve the widest gap, 11, at 14.5. The largest gap becomes 5.5.
Example 3
- Input
stations = [1, 2, 3, 4], k = 3- Output
0.50000- Why
- Each of the three unit gaps gets one station in its middle.
Constraints
2 <= stations.length <= 20000 <= stations[i] <= 10^8stationsis strictly increasing.1 <= k <= 10^6- Answers within
10^-6of the true value are accepted.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (greedy, linear scan per station) | O(k·n) | O(n) |
| Better (greedy with a max-heap) | O(n + k log n) | O(n) |
| Optimal (binary search on the answer) | O(n log(W / ε)) | O(1) |
1Brute force (greedy, linear scan per station)
O(k·n)k placements, each scanning all n - 1 gaps.O(n)One counter per gap.Keep, for every gap, how many new stations it has received. Each new station goes into the gap whose current piece length gap / (count + 1) is the largest. Find that gap with a full scan every time.
- count[i] = 0 for every gap i between stations[i] and stations[i + 1].
- Repeat k times: scan all gaps, pick the one with the largest gap / (count + 1), and increase its count.
- Return the largest gap / (count + 1) over all gaps.
class Solution {
public double minmaxGasDist(int[] stations, int k) {
int n = stations.length;
int[] count = new int[n - 1];
for (int s = 0; s < k; s++) {
int best = 0;
for (int i = 1; i < n - 1; i++) {
double cur = (double) (stations[i + 1] - stations[i]) / (count[i] + 1);
double top = (double) (stations[best + 1] - stations[best]) / (count[best] + 1);
if (cur > top) {
best = i;
}
}
count[best]++;
}
double ans = 0;
for (int i = 0; i < n - 1; i++) {
ans = Math.max(ans, (double) (stations[i + 1] - stations[i]) / (count[i] + 1));
}
return ans;
}
}class Solution:
def minmaxGasDist(self, stations: List[int], k: int) -> float:
n = len(stations)
gaps = [stations[i + 1] - stations[i] for i in range(n - 1)]
count = [0] * (n - 1)
for _ in range(k):
best = 0
for i in range(1, n - 1):
if gaps[i] / (count[i] + 1) > gaps[best] / (count[best] + 1):
best = i
count[best] += 1
return max(gaps[i] / (count[i] + 1) for i in range(n - 1))class Solution {
public:
double minmaxGasDist(vector<int>& stations, int k) {
int n = stations.size();
vector<int> count(n - 1, 0);
for (int s = 0; s < k; s++) {
int best = 0;
for (int i = 1; i < n - 1; i++) {
double cur = (double)(stations[i + 1] - stations[i]) / (count[i] + 1);
double top = (double)(stations[best + 1] - stations[best]) / (count[best] + 1);
if (cur > top) {
best = i;
}
}
count[best]++;
}
double ans = 0;
for (int i = 0; i < n - 1; i++) {
ans = max(ans, (double)(stations[i + 1] - stations[i]) / (count[i] + 1));
}
return ans;
}
};function minmaxGasDist(stations, k) {
const n = stations.length;
const count = new Array(n - 1).fill(0);
for (let s = 0; s < k; s++) {
let best = 0;
for (let i = 1; i < n - 1; i++) {
const cur = (stations[i + 1] - stations[i]) / (count[i] + 1);
const top = (stations[best + 1] - stations[best]) / (count[best] + 1);
if (cur > top) {
best = i;
}
}
count[best]++;
}
let ans = 0;
for (let i = 0; i < n - 1; i++) {
ans = Math.max(ans, (stations[i + 1] - stations[i]) / (count[i] + 1));
}
return ans;
}2Better (greedy with a max-heap)
O(n + k log n)Each of the k placements is one pop and one push on a heap of n - 1 gaps.O(n)The heap and the counters hold one entry per gap.Same greedy rule, but keep the gaps in a max-heap ordered by their current piece length gap / (count + 1). The top of the heap is always the gap that should get the next station.
- Push every gap index into a max-heap keyed by gap / (count + 1), with count = 0.
- Repeat k times: pop the top gap, increase its count, push it back with the new key.
- The key on top of the heap is the answer.
class Solution {
public double minmaxGasDist(int[] stations, int k) {
int n = stations.length;
int[] count = new int[n - 1];
double[] gap = new double[n - 1];
for (int i = 0; i < n - 1; i++) {
gap[i] = stations[i + 1] - stations[i];
}
PriorityQueue<Integer> pq = new PriorityQueue<>(
(a, b) -> Double.compare(gap[b] / (count[b] + 1), gap[a] / (count[a] + 1)));
for (int i = 0; i < n - 1; i++) {
pq.add(i);
}
for (int s = 0; s < k; s++) {
int i = pq.poll();
count[i]++;
pq.add(i);
}
int top = pq.peek();
return gap[top] / (count[top] + 1);
}
}class Solution:
def minmaxGasDist(self, stations: List[int], k: int) -> float:
n = len(stations)
gaps = [stations[i + 1] - stations[i] for i in range(n - 1)]
count = [0] * (n - 1)
heap = [(-gaps[i], i) for i in range(n - 1)]
heapq.heapify(heap)
for _ in range(k):
_, i = heapq.heappop(heap)
count[i] += 1
heapq.heappush(heap, (-gaps[i] / (count[i] + 1), i))
return -heap[0][0]class Solution {
public:
double minmaxGasDist(vector<int>& stations, int k) {
int n = stations.size();
vector<int> count(n - 1, 0);
priority_queue<pair<double, int>> pq; // (piece length, gap index)
for (int i = 0; i < n - 1; i++) {
pq.push({(double)(stations[i + 1] - stations[i]), i});
}
for (int s = 0; s < k; s++) {
int i = pq.top().second;
pq.pop();
count[i]++;
pq.push({(double)(stations[i + 1] - stations[i]) / (count[i] + 1), i});
}
return pq.top().first;
}
};function minmaxGasDist(stations, k) {
const n = stations.length;
const count = new Array(n - 1).fill(0);
const key = (i) => (stations[i + 1] - stations[i]) / (count[i] + 1);
const heap = []; // max-heap of gap indices by key
const up = (j) => {
while (j > 0) {
const p = (j - 1) >> 1;
if (key(heap[p]) >= key(heap[j])) break;
[heap[p], heap[j]] = [heap[j], heap[p]];
j = p;
}
};
const down = (j) => {
while (true) {
let b = j;
const l = 2 * j + 1, r = l + 1;
if (l < heap.length && key(heap[l]) > key(heap[b])) b = l;
if (r < heap.length && key(heap[r]) > key(heap[b])) b = r;
if (b === j) return;
[heap[b], heap[j]] = [heap[j], heap[b]];
j = b;
}
};
for (let i = 0; i < n - 1; i++) {
heap.push(i);
up(heap.length - 1);
}
for (let s = 0; s < k; s++) {
count[heap[0]]++; // its key only shrinks, so sift it down
down(0);
}
return key(heap[0]);
}3Optimal (binary search on the answer)
O(n log(W / ε))About log2(10^8 / 10^-6) ≈ 47 rounds, each a single pass over the n - 1 gaps (W is the widest gap, ε = 10^-6).O(1)Only the bounds and a running count.Guess a maximum distance D. A gap of length g needs floor(g / D) new stations to bring every piece down to at most D. Add that up over all gaps: if the total is at most k, D is achievable. Achievability is monotonic in D, so binary search D on real numbers until the range is narrower than 10^-6.
- lo = 0, hi = the largest gap (no new stations needed for that D).
- While hi - lo > 10^-6: mid = (lo + hi) / 2.
- needed = sum of floor(gap / mid) over all gaps (stop early once it passes k).
- If needed <= k, mid works: hi = mid. Otherwise lo = mid.
- Return hi.
class Solution {
public double minmaxGasDist(int[] stations, int k) {
double lo = 0, hi = 0;
for (int i = 0; i + 1 < stations.length; i++) {
hi = Math.max(hi, stations[i + 1] - stations[i]);
}
while (hi - lo > 1e-6) {
double mid = (lo + hi) / 2;
if (feasible(stations, k, mid)) {
hi = mid;
} else {
lo = mid;
}
}
return hi;
}
private boolean feasible(int[] stations, int k, double d) {
long needed = 0;
for (int i = 0; i + 1 < stations.length; i++) {
needed += (long) ((stations[i + 1] - stations[i]) / d);
if (needed > k) {
return false;
}
}
return true;
}
}class Solution:
def minmaxGasDist(self, stations: List[int], k: int) -> float:
gaps = [stations[i + 1] - stations[i] for i in range(len(stations) - 1)]
lo, hi = 0.0, float(max(gaps))
while hi - lo > 1e-6:
mid = (lo + hi) / 2
if self.feasible(gaps, k, mid):
hi = mid
else:
lo = mid
return hi
def feasible(self, gaps: List[int], k: int, d: float) -> bool:
needed = 0
for g in gaps:
needed += int(g / d)
if needed > k:
return False
return Trueclass Solution {
public:
double minmaxGasDist(vector<int>& stations, int k) {
double lo = 0, hi = 0;
for (int i = 0; i + 1 < (int)stations.size(); i++) {
hi = max(hi, (double)(stations[i + 1] - stations[i]));
}
while (hi - lo > 1e-6) {
double mid = (lo + hi) / 2;
if (feasible(stations, k, mid)) {
hi = mid;
} else {
lo = mid;
}
}
return hi;
}
private:
bool feasible(const vector<int>& stations, int k, double d) {
long long needed = 0;
for (int i = 0; i + 1 < (int)stations.size(); i++) {
needed += (long long)((stations[i + 1] - stations[i]) / d);
if (needed > k) {
return false;
}
}
return true;
}
};function minmaxGasDist(stations, k) {
let lo = 0, hi = 0;
for (let i = 0; i + 1 < stations.length; i++) {
hi = Math.max(hi, stations[i + 1] - stations[i]);
}
while (hi - lo > 1e-6) {
const mid = (lo + hi) / 2;
if (feasible(stations, k, mid)) {
hi = mid;
} else {
lo = mid;
}
}
return hi;
}
function feasible(stations, k, d) {
let needed = 0;
for (let i = 0; i + 1 < stations.length; i++) {
needed += Math.floor((stations[i + 1] - stations[i]) / d);
if (needed > k) {
return false;
}
}
return true;
}Edge cases to test
- Only two stations: the answer is the gap divided by k + 1
- One huge gap among many tiny ones: all new stations go into the huge gap
- All gaps equal and k not a multiple of the number of gaps
- Very large k (10^6), which rules out adding stations one at a time with a linear scan
Hints
Hint 1
New stations inside one gap should always be spread evenly: a gap of length g with c new stations has largest piece g / (c + 1).
Hint 2
Greedy: each new station should go into the gap whose current largest piece is the biggest. A max-heap finds that gap fast.
Hint 3
Flip the question: for a target distance D, how many stations does each gap need? That count only goes down as D grows, so binary search on D.
FAQ
What is the best time complexity for Minimize Max Distance to Gas Station?
Optimal (binary search on the answer) runs in O(n log(W / ε)) time and O(1) extra space. About log2(10^8 / 10^-6) ≈ 47 rounds, each a single pass over the n - 1 gaps (W is the widest gap, ε = 10^-6).
Which pattern does Minimize Max Distance to Gas Station use?
It is a binary search problem that uses the binary search on answer space pattern. Other problems with the same pattern: Koko Eating Bananas, Minimum Number of Days to Make m Bouquets, Separate Squares I.
Is there a brute force solution for Minimize Max Distance to Gas Station?
Yes. Brute force (greedy, linear scan per station) takes O(k·n) time and O(n) space. Keep, for every gap, how many new stations it has received.
Which edge cases should I test for Minimize Max Distance to Gas Station?
Only two stations: the answer is the gap divided by k + 1; One huge gap among many tiny ones: all new stations go into the huge gap; All gaps equal and k not a multiple of the number of gaps; Very large k (10^6), which rules out adding stations one at a time with a linear scan.