Minimize Max Distance to Gas Station Problem

Problem

On a horizontal number line, we have gas stations at positions stations[0], stations[1], ..., stations[N-1], where N = stations.length.

Now, we add K more gas stations so that D, the maximum distance between adjacent gas stations, is minimized.

Return the smallest possible value of D.

Examples

Example:

1
2
3
4

Input:
stations = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], K = 9
Output:
 0.500000

Solution

Method 1 – Feasibility Check with Binary Search

Intuition

We want to minimize the maximum distance D between adjacent gas stations after adding K more stations. If we try a value for D, we can check if it’s possible to add at most K stations so that no gap exceeds D. If yes, try a smaller D; if not, try a larger D. This is a classic binary search on the answer.

Approach

  1. Set low to 0 and high to the maximum distance between stations.
  2. Use binary search to find the smallest D such that we can add at most K stations to make all gaps ≤ D.
  3. For each D, count how many stations are needed for each gap: stations_needed = ceil(gap / D) - 1.
  4. If the total needed is ≤ K, D is feasible.
  5. Continue until the difference between low and high is within a small epsilon (e.g., 1e-6).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
    double minmaxGasDist(vector<int>& s, int k) {
        double l = 0, r = s.back() - s.front(), eps = 1e-6;
        while (r - l > eps) {
            double m = (l + r) / 2, cnt = 0;
            for (int i = 1; i < s.size(); ++i)
                cnt += ceil((s[i] - s[i-1]) / m) - 1;
            if (cnt > k) l = m;
            else r = m;
        }
        return l;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

import "math"
func minmaxGasDist(s []int, k int) float64 {
    l, r := 0.0, float64(s[len(s)-1]-s[0])
    eps := 1e-6
    for r-l > eps {
        m := (l + r) / 2
        cnt := 0
        for i := 1; i < len(s); i++ {
            cnt += int(math.Ceil(float64(s[i]-s[i-1])/m)) - 1
        }
        if cnt > k {
            l = m
        } else {
            r = m
        }
    }
    return l
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    public double minmaxGasDist(int[] s, int k) {
        double l = 0, r = s[s.length-1] - s[0], eps = 1e-6;
        while (r - l > eps) {
            double m = (l + r) / 2;
            int cnt = 0;
            for (int i = 1; i < s.length; i++)
                cnt += (int)Math.ceil((s[i] - s[i-1]) / m) - 1;
            if (cnt > k) l = m;
            else r = m;
        }
        return l;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    fun minmaxGasDist(s: IntArray, k: Int): Double {
        var l = 0.0
        var r = (s.last() - s.first()).toDouble()
        val eps = 1e-6
        while (r - l > eps) {
            val m = (l + r) / 2
            var cnt = 0
            for (i in 1 until s.size)
                cnt += Math.ceil((s[i] - s[i-1]) / m).toInt() - 1
            if (cnt > k) l = m
            else r = m
        }
        return l
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

import math
class Solution:
    def minmaxGasDist(self, s: list[int], k: int) -> float:
        l, r = 0, s[-1] - s[0]
        eps = 1e-6
        while r - l > eps:
            m = (l + r) / 2
            cnt = 0
            for i in range(1, len(s)):
                cnt += math.ceil((s[i] - s[i-1]) / m) - 1
            if cnt > k:
                l = m
            else:
                r = m
        return l
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

impl Solution {
    pub fn minmax_gas_dist(s: Vec<i32>, k: i32) -> f64 {
        let (mut l, mut r) = (0.0, (s[s.len()-1] - s[0]) as f64);
        let eps = 1e-6;
        while r - l > eps {
            let m = (l + r) / 2.0;
            let mut cnt = 0;
            for i in 1..s.len() {
                cnt += ((s[i] - s[i-1]) as f64 / m).ceil() as i32 - 1;
            }
            if cnt > k {
                l = m;
            } else {
                r = m;
            }
        }
        l
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    minmaxGasDist(s: number[], k: number): number {
        let l = 0, r = s[s.length-1] - s[0], eps = 1e-6;
        while (r - l > eps) {
            let m = (l + r) / 2, cnt = 0;
            for (let i = 1; i < s.length; i++)
                cnt += Math.ceil((s[i] - s[i-1]) / m) - 1;
            if (cnt > k) l = m;
            else r = m;
        }
        return l;
    }
}

Complexity

  • ⏰ Time complexity: O(n log(max_gap/eps)), where n is the number of stations and eps is the precision.
  • 🧺 Space complexity: O(1), only constant extra space is used.