Minimize Max Distance to Gas Station | GFG Practice | Optimal Binary Search

The “Minimize Max Distance to Gas Station” problem is a classic example of using binary search on real numbers (floating point search) to optimize distances.

In this blog, we’ll explain the problem, walk you through both brute force and optimal solutions, and make everything easy to understand with code comments, dry runs, and clear explanations.

Here’s the [Problem Link] to begin with.

Problem Statement

We have a horizontal number line. On that number line, we have gas stations at positions stations[0], stations[1], …, stations[n-1], where n is the size of the stations array. Now, we add k more gas stations so that d, the maximum distance between adjacent gas stations, is minimized. We have to find the smallest possible value of d. Find the answer exactly to 2 decimal places.
Note: stations is in a strictly increasing order.

Example 1

Input:
n = 10
stations[] = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
k = 9
Output: 0.50
Explanation: Each of the 9 stations can be added mid way between all the existing adjacent stations.

Example 2

Input:
n = 10
stations[] = [3, 6, 12, 19, 33, 44, 67, 72, 89, 95] 
k = 2 
Output: 14.00 
Explanation: Construction of gas stations at 8th(between 72 and 89) and 6th(between 44 and 67) locations.

Your Task:
You don’t need to read input or print anything. Your task is to complete the function findSmallestMaxDist() which takes a list of stations and integer k as inputs and returns the smallest possible value of d. Find the answer exactly to 2 decimal places.

Constraint:
10 <= n <= 10000 
0 <= stations[i] <= 10⁹ 
0 <= k <= 10⁵

Brute Force Solution (Try Every Possible Distance)

Intuition and Approach

Let’s solve the problem in the most straightforward way:

1. Try Every Possible Distance:
   Start from a small distance (like 0.01) and increase by small steps up to the largest gap between stations.
2. Check If Placement Is Possible:
   For each distance, check if you can add at most k stations so that no gap is larger than this distance.
3. Return the First Valid Distance:
   The first distance for which placement is possible is our answer.
4. Why does this work?
   We check every possible distance, so we’re sure to find the smallest one that works.

This approach is easy to understand but not efficient for large inputs or high precision.

Code Implementation

class Solution:
    def canPlace(self, stations, k, d):
        needed = 0
        for i in range(1, len(stations)):
            gap = stations[i] - stations[i - 1]
            needed += int(gap // d)  # How many extra stations needed in this gap
        return needed <= k

    def findSmallestMaxDist(self, stations, k):
        max_gap = max(stations[i + 1] - stations[i] for i in range(len(stations) - 1))
        d = 0.01
        while d <= max_gap:
            if self.canPlace(stations, k, d):
                return round(d, 2)  # Return as float, rounded to 2 decimals
            d += 0.01
        return round(max_gap, 2)

Code Explanation

• For each possible distance d, check if you can add at most k stations so that no gap is bigger than d.
• The helper function canPlace counts how many new stations are needed for a given d.
• Return the first d that works.

Dry Run

Input:
stations = [1], k = 9

• Try d = 0.01, 0.02, …, 1.00
• At d = 1.00, you need 9 new stations (at positions 2, 3, …, 9), which is allowed.
• Return 1.00

Final Output:
1.00

Time and Space Complexity

• Time Complexity: O((max_gap / step) * n)
  For each possible distance, we check all gaps.
• Space Complexity: O(1)
  Only variables for counting.

Conclusion

The brute force approach is simple and works for small inputs or low precision, but it’s too slow for large values or high precision.

Optimal Solution (Binary Search on Answer)

Intuition and Approach

We can do much better using binary search on the answer (floating point search):

1. Binary Search on Distance:
   The answer lies between 0 and the largest gap between stations. Use binary search to find the smallest maximum distance.
2. Check If Placement Is Possible:
   For each mid value (distance), check if you can add at most k stations so that no gap is bigger than this distance.
3. Adjust Search Window:
   • If placement is possible, try a smaller distance.
   • If not, try a larger distance.
4. Why does this work?
   The function is monotonic: as the distance increases, it becomes easier to place all stations. Binary search is perfect for this.

Code Implementation

class Solution:
    def canPlace(self, stations, k, dist):
        needed = 0
        for i in range(1, len(stations)):
            gap = stations[i] - stations[i-1]
            # Number of additional stations needed in this gap
            needed += int(gap / dist)
        return needed <= k

    def findSmallestMaxDist(self, stations, k):
        left, right = 0.0, max(stations[i+1] - stations[i] for i in range(len(stations)-1))
        # Binary search with precision up to 1e-6
        while right - left > 1e-6:
            mid = (left + right) / 2
            if self.canPlace(stations, k, mid):
                right = mid
            else:
                left = mid
        # Round to 2 decimal places as required
        return round(right, 2)

Code Explanation

• Use binary search between 0 and the maximum gap.
• For each mid distance, check if you can add at most k stations.
• If you can, try a smaller distance.
• If not, try a larger distance.
• Keep searching until the difference is very small (high precision).
• Return the smallest valid distance, rounded to 2 decimals.

Dry Run

Input:
stations = [1], k = 9

• left = 0.0, right = 9.0
• mid = 4.5, need 1 station (not enough, try smaller)
• mid = 2.25, need 3 stations (not enough, try smaller)
• …
• mid = 1.00, need 9 stations (just right)
• Loop ends, answer is 1.00

Final Output:
1.00

Time and Space Complexity

• Time Complexity: O(n * log(max_gap / precision))
  Binary search on distance, checking all gaps for each guess.
• Space Complexity: O(1)
  Only variables for counting.

Conclusion

The optimal solution is efficient and works well for large arrays and high precision. It’s the best approach for interviews and practical use.

Final Thoughts

The “Minimize Max Distance to Gas Station” problem is a great example of using binary search on real numbers to optimize placement. Start with brute force to understand the basics, then use binary search for best performance and precision.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.