Time Complexity: $O(k \log N)$, where $N$ is the number of stations and $k$ is the number of added stations.

Why it fails:

1. Inefficiency with Large K: The value of k can be up to $10^6$ (or larger in similar variants). Performing heap operations this many times is computationally expensive.
2. Suboptimal Splits: Simply splitting the largest gap in half is not always the optimal move for the final distribution. For example, if one gap is 10.0 and another is 3.3, and we have 2 stations, splitting 10.0 twice (10 -> 5 -> 2.5) is better than splitting 10 once and 3.3 once. The greedy "split in half" logic requires complex tracking of how many stations are assigned to each original gap to work correctly with floating-point precision, making the implementation error-prone and slow.

Core Insight for Minimize Max Distance to Gas Station

The critical realization is that we do not need to decide where to place the stations one by one. Instead, we can guess a candidate value for the maximum distance, let's call it mid, and check if it is possible to achieve this maximum distance using at most k new stations.

The Condition Function: Given a target max distance mid, how many new stations do we need? Iterate through every adjacent pair of existing stations. If the distance between stations[i] and stations[i+1] is gap:

• If gap <= mid, we don't need to add any stations in this interval.
• If gap > mid, we need to insert enough stations to ensure no segment exceeds mid. The number of segments required is ceil(gap / mid). Therefore, the number of cuts (new stations) required is ceil(gap / mid) - 1.

Visual Description: Imagine the number line with existing stations as fixed points. We propose a "ruler" of length mid. We measure each gap with this ruler. If a gap is larger than the ruler, we calculate how many times the ruler fits into that gap. The total count of these fits (minus one per gap) tells us the total new stations required. If this total is $\le k$, then mid is a feasible answer, and we try to find an even smaller mid. If the total is $> k$, our mid was too ambitious (too small), and we must increase it.

Execution Flow

1. Initialization:
   • Set low = 0.
   • Set high = maximum difference between adjacent elements in stations.
2. Search Process:
   • While high - low > 1e-6:
     1. Calculate mid = (low + high) / 2.
     2. Initialize required_stations = 0.
     3. Iterate through the stations array from index 0 to n-2:
        • Calculate gap = stations[i+1] - stations[i].
        • Add ceil(gap / mid) - 1 to required_stations.
     4. Decision:
        • If required_stations <= k: Set high = mid (Try to minimize distance further).
        • Else: Set low = mid (Need a larger distance to satisfy k).
3. Termination:
   • Return high (or low, as they have converged).

Proof of Correctness

The algorithm relies on the monotonicity of the condition function. Let $F(d)$ be the minimum number of stations required to ensure the max distance is at most $d$.

• As $d$ decreases (tighter constraint), $F(d)$ increases (we need more stations).
• As $d$ increases (looser constraint), $F(d)$ decreases.

Since we want the smallest $d$ such that $F(d) \le k$, and the function is monotonic, binary search is guaranteed to find the boundary between feasible and infeasible values within the specified precision. The calculation ceil(gap / mid) - 1 mathematically guarantees the minimum cuts needed for a single interval, ensuring the greedy accumulation is optimal for the check function.

Reference Implementation

C++ Solution for LeetCode 774

cpp
#include <vector>
#include <cmath>
#include <algorithm>

class Solution {
public:
    double minmaxGasDist(std::vector<int>& stations, int k) {
        double low = 0;
        double high = 0;
        
        // Initialize high to the maximum existing gap
        for (size_t i = 0; i < stations.size() - 1; ++i) {
            high = std::max(high, (double)(stations[i+1] - stations[i]));
        }

        // Binary search on the answer (distance)
        // Loop until the search range is sufficiently small
        while (high - low > 1e-6) {
            double mid = low + (high - low) / 2.0;
            if (mid < 1e-9) { // Avoid division by zero
                low = mid;
                continue;
            }
            
            if (canAchieve(stations, k, mid)) {
                high = mid; // Try smaller distance
            } else {
                low = mid; // Need larger distance
            }
        }
        
        return high;
    }

private:
    // Helper function to check if max distance 'mid' is possible with 'k' stations
    bool canAchieve(const std::vector<int>& stations, int k, double mid) {
        int required = 0;
        for (size_t i = 0; i < stations.size() - 1; ++i) {
            double gap = stations[i+1] - stations[i];
            // Calculate stations needed for this gap
            // ceil(gap / mid) - 1 gives the count of added stations
            required += (int)ceil(gap / mid) - 1;
        }
        return required <= k;
    }
};

Java Solution for LeetCode 774

java
class Solution {
    public double minmaxGasDist(int[] stations, int k) {
        double low = 0;
        double high = 0;
        
        // Find the initial maximum gap
        for (int i = 0; i < stations.length - 1; i++) {
            high = Math.max(high, stations[i+1] - stations[i]);
        }
        
        // Binary Search until precision limit
        while (high - low > 1e-6) {
            double mid = low + (high - low) / 2.0;
            
            if (mid < 1e-9) { 
                low = mid;
                continue;
            }

            if (canAchieve(stations, k, mid)) {
                high = mid; // Feasible, try smaller
            } else {
                low = mid; // Not feasible, need larger
            }
        }
        
        return high;
    }
    
    private boolean canAchieve(int[] stations, int k, double mid) {
        int count = 0;
        for (int i = 0; i < stations.length - 1; i++) {
            double gap = stations[i+1] - stations[i];
            // Calculate how many stations fit in this gap
            count += (int)Math.ceil(gap / mid) - 1;
        }
        return count <= k;
    }
}

Python Solution for LeetCode 774

python
import math

class Solution:
    def minmaxGasDist(self, stations: list[int], k: int) -> float:
        # Define the condition function
        def can_achieve(mid_dist):
            count = 0
            for i in range(len(stations) - 1):
                gap = stations[i+1] - stations[i]
                # Calculate number of cuts needed for this gap
                # If gap is 10 and mid is 3, we need ceil(3.33) - 1 = 3 stations
                count += math.ceil(gap / mid_dist) - 1
            return count <= k

        low = 0
        # High can be the max gap or simply the total range
        high = stations[-1] - stations[0]
        
        # Binary search for the minimal max distance
        while high - low > 1e-6:
            mid = (low + high) / 2
            if mid < 1e-9: # protection against extremely small mid
                low = mid
                continue
                
            if can_achieve(mid):
                high = mid
            else:
                low = mid
                
        return high