← Back to Index

📚 Minimize Max Distance to Gas Station – Java Cheat Sheet

📌 What Is It?

The Minimize Max Distance to Gas Station problem involves placing additional gas stations along a highway to minimize the maximum distance between adjacent stations. The goal is to determine the smallest possible maximum distance using binary search.

🧱 Pattern Template

class Solution {
    public double minmaxGasDist(int[] stations, int k) {
        double left = 0, right = stations[stations.length - 1] - stations[0];

        while (right - left > 1e-6) {
            double mid = left + (right - left) / 2;

            if (canPlace(stations, k, mid)) {
                right = mid; // Try a smaller maximum distance
            } else {
                left = mid; // Try a larger maximum distance
            }
        }

        return left;
    }

    private boolean canPlace(int[] stations, int k, double maxDist) {
        int count = 0;

        for (int i = 1; i < stations.length; i++) {
            count += (int) ((stations[i] - stations[i - 1]) / maxDist);

            if (count > k) {
                return false;
            }
        }

        return true;
    }
}

📊 Time Complexity

• Binary Search: O(log(D)), where D is the difference between the farthest stations.
• Validation: O(N), where N is the number of stations.
• Overall Complexity: O(N log(D)).

✅ Use Cases

• Optimizing placement of resources along a linear path
• Applications in transportation and logistics

📘 Common LeetCode Problems

• 774. Minimize Max Distance to Gas Station [Hard] Binary Search

🧪 Example: Minimize Max Distance to Gas Station

Input: stations = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 9
Output: 0.500000

Explanation:
- Place 9 additional stations to minimize the maximum distance to 0.5.

▶️ View Animation

💡 Pro Tips

• Use binary search to efficiently find the smallest possible maximum distance.
• Edge cases: very small or very large distances, or when no additional stations are needed.
• Use a precision threshold (e.g., 1e-6) to terminate the binary search.