Minimize max distance to gas station

Array Binary Search

53.9% acceptance

Mar 31, 2026

712

104

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.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn minmax_gas_dist(stations: Vec<i32>, k: i32) -> f64 {
    let gaps: Vec<f64> = stations.windows(2)
      .map(|w| (w[1] - w[0]) as f64)
      .collect();
    let mut lo = 0.0f64;
    let mut hi = gaps.iter().cloned().fold(0.0f64, f64::max);
    for _ in 0..100 {
      let mid = (lo + hi) / 2.0;
      let needed: i64 = gaps.iter().map(|&g| (g / mid).ceil() as i64 - 1).sum();
      if needed <= k as i64 { hi = mid; } else { lo = mid; }
    }
    hi
  }
}