774. Minimize Max Distance to Gas Station

Problem Description

You have gas stations positioned along a straight line (x-axis), represented by an integer array stations where each element indicates the position of a gas station.

Your task is to add exactly k new gas stations. These new stations can be placed at any position on the x-axis, including non-integer positions (like 3.5 or 7.25).

After adding all k new stations, you need to minimize the "penalty", which is defined as the maximum distance between any two adjacent gas stations (including both original and newly added stations).

For example, if you have stations at positions [1, 5, 10] and the distances between adjacent stations are 4 (between 1 and 5) and 5 (between 5 and 10), the penalty would be 5 (the maximum distance). By adding new stations strategically, you can reduce this maximum distance.

The goal is to find the optimal placement of k new stations such that the penalty (maximum distance between adjacent stations) is as small as possible. Return this minimum possible penalty value.

The answer will be accepted if it's within 10^-6 of the actual answer, allowing for floating-point precision tolerance.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

The key insight is recognizing that this is an optimization problem where we want to minimize the maximum value - a classic scenario for binary search on the answer.

Think about it this way: if someone tells you "the maximum distance between adjacent stations must be at most x", you can calculate exactly how many new stations you'd need to achieve this. For each existing gap between stations, if the gap is larger than x, you'll need to add stations to break it down into smaller segments of size at most x.

For a gap of size d, the number of new stations needed is floor(d / x). Why? Because we're essentially dividing the gap into segments of size x, and the number of divisions tells us how many stations to insert.

This creates a monotonic relationship: as x decreases (we want smaller maximum distance), the number of required stations increases. Conversely, as x increases (we allow larger maximum distance), fewer stations are needed.

Since we have exactly k stations to add, we're looking for the smallest value of x such that we need at most k stations to ensure no gap exceeds x. This is perfect for binary search:

If a certain maximum distance x requires more than k stations, then x is too small
If it requires k or fewer stations, then x is feasible and we can try an even smaller value

The search space is bounded between 0 (theoretical minimum) and the largest existing gap (or some large value like 10^8). We keep narrowing down this range until we converge on the optimal maximum distance, using a precision threshold of 10^-6 to determine when to stop.

Learn more about Binary Search patterns.

Solution Implementation

1class Solution: 2 def minmaxGasDist(self, stations: List[int], k: int) -> float: 3 """ 4 Find the minimum possible maximum distance between adjacent gas stations 5 after adding k new stations optimally. 6 7 Args: 8 stations: List of positions of existing gas stations (sorted) 9 k: Number of new gas stations to add 10 11 Returns: 12 Minimum possible maximum distance between adjacent stations 13 """ 14 15 def can_achieve_max_distance(max_dist: float) -> bool: 16 """ 17 Check if we can achieve a maximum distance of max_dist between 18 adjacent stations by adding at most k new stations. 19 20 For each gap between existing stations, calculate how many new 21 stations we need to ensure no gap exceeds max_dist. 22 """ 23 total_stations_needed = 0 24 25 # Check each consecutive pair of existing stations 26 for i in range(len(stations) - 1): 27 gap = stations[i + 1] - stations[i] 28 # Calculate stations needed to make this gap <= max_dist 29 # Using int() for floor division of the gap by max_dist 30 stations_needed = int(gap / max_dist) 31 total_stations_needed += stations_needed 32 33 # Return true if we can achieve this with k or fewer stations 34 return total_stations_needed <= k 35 36 # Binary search on the answer (maximum distance) 37 # Left bound: 0 (minimum possible distance) 38 # Right bound: 1e8 (large enough for any reasonable input) 39 left, right = 0.0, 1e8 40 41 # Continue binary search until precision is sufficient (1e-6) 42 while right - left > 1e-6: 43 mid = (left + right) / 2 44 45 # If we can achieve max distance of mid with k stations 46 if can_achieve_max_distance(mid): 47 # Try to find a smaller maximum distance 48 right = mid 49 else: 50 # Need a larger maximum distance 51 left = mid 52 53 return left 54

1class Solution { 2 /** 3 * Minimizes the maximum distance between adjacent gas stations after adding k new stations. 4 * Uses binary search on the answer to find the minimum possible maximum distance. 5 * 6 * @param stations Array of existing gas station positions on x-axis 7 * @param k Number of new gas stations to add 8 * @return Minimum possible maximum distance between adjacent stations 9 */ 10 public double minmaxGasDist(int[] stations, int k) { 11 // Binary search bounds: left = 0, right = 1e8 (large enough upper bound) 12 double left = 0; 13 double right = 1e8; 14 15 // Binary search with precision of 1e-6 16 while (right - left > 1e-6) { 17 double mid = (left + right) / 2.0; 18 19 // Check if we can achieve maximum distance of 'mid' with k stations 20 if (canAchieveMaxDistance(mid, stations, k)) { 21 // If possible, try to find a smaller maximum distance 22 right = mid; 23 } else { 24 // If not possible, we need a larger maximum distance 25 left = mid; 26 } 27 } 28 29 return left; 30 } 31 32 /** 33 * Checks if it's possible to add stations such that maximum distance is at most maxDistance. 34 * 35 * @param maxDistance Target maximum distance between adjacent stations 36 * @param stations Array of existing gas station positions 37 * @param k Number of available new stations 38 * @return true if achievable with k or fewer stations, false otherwise 39 */ 40 private boolean canAchieveMaxDistance(double maxDistance, int[] stations, int k) { 41 int requiredStations = 0; 42 43 // Calculate minimum stations needed between each pair of existing stations 44 for (int i = 0; i < stations.length - 1; i++) { 45 // Distance between current and next station 46 double distance = stations[i + 1] - stations[i]; 47 48 // Number of new stations needed to ensure max gap is at most maxDistance 49 // Using floor division to get minimum stations needed 50 requiredStations += (int) (distance / maxDistance); 51 } 52 53 // Check if required stations is within our budget 54 return requiredStations <= k; 55 } 56} 57

1class Solution { 2public: 3 double minmaxGasDist(vector<int>& stations, int k) { 4 // Binary search bounds: minimum and maximum possible distances 5 double left = 0.0; 6 double right = 1e8; 7 8 // Lambda function to check if a given max distance is achievable 9 // with at most k additional stations 10 auto canAchieveMaxDistance = [&](double maxDistance) { 11 int requiredStations = 0; 12 13 // Calculate how many stations needed between each pair of existing stations 14 for (int i = 0; i < stations.size() - 1; ++i) { 15 double gap = stations[i + 1] - stations[i]; 16 // Number of stations needed to ensure no gap exceeds maxDistance 17 requiredStations += static_cast<int>(gap / maxDistance); 18 } 19 20 // Check if we can achieve this with k or fewer stations 21 return requiredStations <= k; 22 }; 23 24 // Binary search with precision of 1e-6 25 while (right - left > 1e-6) { 26 double mid = (left + right) / 2.0; 27 28 // If we can achieve mid as max distance, try smaller values 29 if (canAchieveMaxDistance(mid)) { 30 right = mid; 31 } 32 // Otherwise, we need a larger max distance 33 else { 34 left = mid; 35 } 36 } 37 38 // Return the minimum achievable maximum distance 39 return left; 40 } 41}; 42

1function minmaxGasDist(stations: number[], k: number): number { 2 // Binary search bounds: minimum and maximum possible distances 3 let left: number = 0.0; 4 let right: number = 1e8; 5 6 // Helper function to check if a given max distance is achievable 7 // with at most k additional stations 8 const canAchieveMaxDistance = (maxDistance: number): boolean => { 9 let requiredStations: number = 0; 10 11 // Calculate how many stations needed between each pair of existing stations 12 for (let i = 0; i < stations.length - 1; i++) { 13 const gap: number = stations[i + 1] - stations[i]; 14 // Number of stations needed to ensure no gap exceeds maxDistance 15 // Using Math.floor to get integer division result 16 requiredStations += Math.floor(gap / maxDistance); 17 } 18 19 // Check if we can achieve this with k or fewer stations 20 return requiredStations <= k; 21 }; 22 23 // Binary search with precision of 1e-6 24 while (right - left > 1e-6) { 25 const mid: number = (left + right) / 2.0; 26 27 // If we can achieve mid as max distance, try smaller values 28 if (canAchieveMaxDistance(mid)) { 29 right = mid; 30 } 31 // Otherwise, we need a larger max distance 32 else { 33 left = mid; 34 } 35 } 36 37 // Return the minimum achievable maximum distance 38 return left; 39} 40

Solution Approach

The solution implements binary search on the answer space using the boundary-finding template pattern, adapted for floating-point precision.

Defining the Feasible Function

For this problem, feasible(x) returns true if we can achieve a maximum distance of x using at most k new stations.

This creates a boolean pattern across possible distances:

distance: 0.1 0.5 1.0 2.0 3.0 4.0 ... feasible: false false false true true true ...

We want to find the first true value - the minimum distance that is feasible.

Binary Search Template (Floating-Point Adaptation)

Since this involves floating-point numbers, we adapt the template using precision-based termination:

Initialize left = 0, right = 1e8, and first_true_value = right
While right - left > 1e-6:
- Calculate mid = (left + right) / 2
- If feasible(mid) is true:
  - Record first_true_value = mid as a potential answer
  - Search left: right = mid (look for smaller feasible distance)
- Else:
  - Search right: left = mid
Return first_true_value (or left, which converges to the same value)

Feasible Check Implementation

For each gap between adjacent stations of size d, we need floor(d / x) new stations to ensure no segment exceeds x:

If the gap is 10 and max distance is 3, we need floor(10/3) = 3 stations
This creates 4 segments of sizes ≤ 3

Sum across all gaps and check if total ≤ k.

Why This Works

The feasibility function is monotonic: larger x values require fewer stations. Once we find a feasible x, all larger values are also feasible. Binary search efficiently finds the boundary between infeasible and feasible regions.

Time Complexity: O(n × log(W/ε)) where n is stations count, W is the search range, ε is precision. Space Complexity: O(1)

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a concrete example with stations = [1, 7, 15] and k = 2 new stations to add.

Initial Setup:

Original stations: [1, 7, 15]
Gaps between stations: 7-1=6 and 15-7=8
Current penalty (max gap): 8
We need to add exactly 2 new stations to minimize this penalty

Binary Search Process:

Round 1:

left = 0, right = 100 (using 100 as upper bound for simplicity)
mid = 50
Check if we can achieve max distance of 50 with 2 stations:
- Gap [1, 7]: size 6, needs int(6/50) = 0 stations
- Gap [7, 15]: size 8, needs int(8/50) = 0 stations
- Total needed: 0 stations ≤ 2 ✓
Since feasible, try smaller: right = 50

Round 2:

left = 0, right = 50
mid = 25
Check if we can achieve max distance of 25:
- Gap [1, 7]: needs int(6/25) = 0 stations
- Gap [7, 15]: needs int(8/25) = 0 stations
- Total: 0 stations ≤ 2 ✓
Try smaller: right = 25

Round 3:

left = 0, right = 25
mid = 12.5
Check if we can achieve max distance of 12.5:
- Gap [1, 7]: needs int(6/12.5) = 0 stations
- Gap [7, 15]: needs int(8/12.5) = 0 stations
- Total: 0 stations ≤ 2 ✓
Try smaller: right = 12.5

Round 4:

left = 0, right = 12.5
mid = 6.25
Check if we can achieve max distance of 6.25:
- Gap [1, 7]: needs int(6/6.25) = 0 stations
- Gap [7, 15]: needs int(8/6.25) = 1 station
- Total: 1 station ≤ 2 ✓
Try smaller: right = 6.25

Round 5:

left = 0, right = 6.25
mid = 3.125
Check if we can achieve max distance of 3.125:
- Gap [1, 7]: needs int(6/3.125) = 1 station
- Gap [7, 15]: needs int(8/3.125) = 2 stations
- Total: 3 stations > 2 ✗
Too ambitious, increase: left = 3.125

Round 6:

left = 3.125, right = 6.25
mid = 4.6875
Check if we can achieve max distance of 4.6875:
- Gap [1, 7]: needs int(6/4.6875) = 1 station
- Gap [7, 15]: needs int(8/4.6875) = 1 station
- Total: 2 stations = 2 ✓
Try smaller: right = 4.6875

Continuing... The binary search continues, narrowing the range between left and right until they converge within 1e-6.

Final Result: The algorithm converges to approximately 4.0. With this maximum distance:

We place 1 station in gap [1, 7] at position 4.5 → gaps become [1, 4.5] (size 3.5) and [4.5, 7] (size 2.5)
We place 1 station in gap [7, 15] at position 11 → gaps become [7, 11] (size 4) and [11, 15] (size 4)
Final stations: [1, 4.5, 7, 11, 15]
All gaps: 3.5, 2.5, 4, 4
Maximum gap (penalty): 4.0

This demonstrates how binary search efficiently finds the optimal placement strategy by testing different maximum distance thresholds and checking feasibility.

Time and Space Complexity

Time Complexity: O(n * log(M/ε)) where n is the number of stations, M is the maximum distance between consecutive stations (bounded by 1e8), and ε is the precision (1e-6).

The binary search runs for log((right - left) / ε) = log(1e8 / 1e-6) = log(1e14) iterations, which is approximately 47 iterations.
In each iteration of the binary search, the check function is called.
The check function iterates through all consecutive pairs of stations using pairwise(stations), which takes O(n-1) = O(n) time.
For each pair, it performs a constant time operation: int((b - a) / x).
Therefore, each check call takes O(n) time.
Total time complexity: O(n * log(M/ε))

Space Complexity: O(1) or O(n) depending on the implementation of pairwise.

The binary search uses only a constant amount of extra space for variables left, right, and mid.
The check function uses a generator expression with sum(), which doesn't create an intermediate list.
However, pairwise(stations) may create an iterator that could use O(1) space if implemented efficiently, or O(n) space if it creates intermediate pairs.
In Python 3.10+, itertools.pairwise uses O(1) extra space.
Overall space complexity: O(1) auxiliary space (excluding input).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Using Wrong Binary Search Pattern for Floating-Point

For floating-point binary search, you cannot use the exact integer template (while left <= right with right = mid - 1). You must adapt for continuous values.

Incorrect (integer pattern):

while left <= right: # Will not terminate for floats  mid = (left + right) / 2  if feasible(mid):  right = mid - 1 # Wrong for floating-point  else:  left = mid + 1

Correct (floating-point adaptation):

while right - left > 1e-6: # Precision-based termination  mid = (left + right) / 2  if feasible(mid):  right = mid # No -1 for floats  else:  left = mid # No +1 for floats return left

2. Incorrect Station Counting Formula

Pitfall: Using ceil((b - a) / x) to count new stations needed in a gap. This counts segments, not dividing points.

Example:

Gap: 10 units, max distance: 3 units
Incorrect: ceil(10/3) = 4 stations (creates 5 segments - too many!)
Correct: int(10/3) = 3 stations (creates 4 segments of sizes ≤ 3)

Solution: Use int(gap / max_dist) which correctly calculates the number of cuts needed.

3. Floating-Point Precision Errors

Pitfall: Using exact equality or insufficient precision.

# Wrong: May loop forever while left < right:  ...

Solution: Always use a precision threshold:

while right - left > 1e-6:  ...

4. Binary Search Boundary Issues

Pitfall: Setting right boundary too small when k=0.

Solution: Use a sufficiently large upper bound like 1e8, or handle k=0 as a special case returning the maximum gap directly.

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?

Pre-order traversal

Post-order traversal

In-order traversal

Level-order traversal

I don't know