Code Logo

Minimize Maximum Distance Between Gas Stations

Published at05 Jan 2026
Created by
Medium 10 views
Like20

You are given the positions of existing gas stations on a line, and you may add exactly k more stations anywhere you want. Your goal is to make the largest distance between neighboring stations as small as possible.

This is not about minimizing the total distance. It is about shrinking the worst gap. If one interval is much larger than the rest, that interval controls the answer.

For example, if stations = [1, 2, 10] and k = 2, the best answer is 3.0. By inserting two new stations inside the long gap from 2 to 10, you can split it into pieces of length at most 3. If stations = [1, 10] and k = 1, the best place is the middle, which gives a maximum gap of 4.5.

So the task is to place the new stations so that the worst remaining gap becomes as small as possible.

Example Input & Output

Example 1
Input
stations = [1, 2, 10], k = 2
Output
3.0
Explanation

Adding stations at positions 4 and 7 results in gaps of at most 3.

Example 2
Input
stations = [1, 2, 3, 4, 5, 6, 7, 8, 9], k = 3
Output
1.0
Explanation

Adding 3 stations evenly between existing ones can make all distances at most 1.

Example 3
Input
stations = [1, 10], k = 1
Output
4.5
Explanation

Adding one station at position 5.5 minimizes the maximum gap to 4.5.

Algorithm Flow

Recommendation Algorithm Flow for Minimize Maximum Distance Between Gas Stations
Recommendation Algorithm Flow for Minimize Maximum Distance Between Gas Stations

Solution Approach

This is a binary search on the answer, where the answer is a real number. Suppose we guess that the maximum allowed gap is d. Then we can ask: how many extra stations are needed so every existing gap becomes at most d?

For one gap of length gap, the number of stations needed is:

Math.ceil(gap / d) - 1

If the total number needed across all gaps is at most k, then d is feasible and we can try a smaller value. If it needs more than k stations, then d is too small.

That gives a monotonic yes-or-no condition, which is exactly what binary search needs. We search between 0 and the largest current gap until the interval is small enough for the required precision.

This runs in O(n log R), where R is the search precision range, and it is the standard way to handle optimization problems like this one.

Best Answers

java
class Solution {
    public double minimize_max_distance(int[] stations, int k) {
        double low = 0, high = stations[stations.length - 1] - stations[0];
        for (int i = 0; i < 100; i++) {
            double mid = (low + high) / 2;
            if (check(mid, stations, k)) high = mid;
            else low = mid;
        }
        return high;
    }
    private boolean check(double d, int[] stations, int k) {
        int count = 0;
        for (int i = 0; i < stations.length - 1; i++) {
            count += (int)((stations[i+1] - stations[i]) / d);
        }
        return count <= k;
    }
}