Loading problems...
TL;DR: We use binary search on the potential answer (the maximum distance) to determine the smallest value that satisfies the constraint of adding at most k stations.
In the Minimize Max Distance to Gas Station problem, we are provided with a sorted list of existing gas station positions and an integer k. We must place k new gas stations into the intervals between existing stations such that the largest resulting gap between any two adjacent stations is minimized. This is a classic "min-max" optimization problem often seen in technical interviews at companies like Google.
A naive approach attempts to greedily reduce the largest gap. We could maintain all current gaps in a priority queue (Max Heap). In each step, we extract the largest gap, place a new station in the middle to split it into two smaller gaps, and push those back into the heap. We repeat this process k times.
Pseudo-code:
text
Initialize Max Heap with all adjacent differences (gaps)
Repeat k times:
gap = heap.pop()
new_gap = gap / 2
heap.push(new_gap)
heap.push(new_gap)
Return heap.top()Time Complexity: , where is the number of stations and is the number of added stations.
Why it fails:
k can be up to (or larger in similar variants). Performing heap operations this many times is computationally expensive.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:
gap <= mid, we don't need to add any stations in this interval.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 , then mid is a feasible answer, and we try to find an even smaller mid. If the total is , our mid was too ambitious (too small), and we must increase it.

low = 0.high = maximum difference between adjacent elements in stations.high - low > 1e-6:
mid = (low + high) / 2.required_stations = 0.stations array from index 0 to n-2:
gap = stations[i+1] - stations[i].ceil(gap / mid) - 1 to required_stations.required_stations <= k: Set high = mid (Try to minimize distance further).low = mid (Need a larger distance to satisfy k).high (or low, as they have converged).The algorithm relies on the monotonicity of the condition function. Let be the minimum number of stations required to ensure the max distance is at most .
Since we want the smallest such that , 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.
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; } };
javaclass 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; } }
pythonimport 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
stations array.low, high, mid, count) and do not allocate additional data structures proportional to the input size.The Binary Search on Answer pattern is a powerful tool for optimization problems where the search space is value-based rather than index-based.
D days.m bouquets can be formed.Understanding LeetCode 774 provides the blueprint for solving all these "Minimize the Maximum" or "Maximize the Minimum" problems efficiently.
k times results in . When k is large (), this is significantly slower than the binary search approach.low <= high. Instead, use a fixed precision check high - low > 1e-6 or run the loop for a fixed number of iterations (e.g., 100 times) to guarantee precision.low starts at 0 and the loop calculates mid very close to 0, gap / mid can cause issues. Ensure your logic handles extremely small mid values or start low at a small epsilon like 1e-6 (though starting at 0 is valid if you handle the check carefully).