⚡Flashcard Drill➔
NeetCode #302LC-774HardBinary Search
← Back to All Problems

#302 · #774 · Minimize Max Distance to Gas Station(最小化加油次数)

📌 Problem Statement & Constraints

You are given a sorted array stations of gas station positions and an integer k. You may add k new stations anywhere. Return the smallest possible maximum distance between adjacent stations after adding them. Answers within 10^-6 are accepted. Constraints: 10 <= stations.length <= 2000, 0 <= stations[i] <= 10^8, 1 <= k <= 10^6.

💡 Core Algorithmic Approaches

  1. Binary search on the maximum gap d: "can we achieve a maximum gap of at most d with at most k new stations" is monotone.
  2. For a gap g, the number of new stations needed is ceil(g / d) - 1.
  3. Because the answer is a real number, run a fixed number of iterations (about 100) instead of looping on lo < hi.
  4. The search range is [0, stations[-1] - stations[0]].

💻 Benchmark Python3 Implementation

class Solution:
    def minmaxGasDist(self, stations: List[int], k: int) -> float:
        import math

        def needed(d: float) -> int:
            total = 0
            for i in range(1, len(stations)):
                gap = stations[i] - stations[i - 1]
                # ceil(gap / d) - 1 new stations; the epsilon guards exact division
                total += max(0, math.ceil(gap / d - 1e-9) - 1)
            return total

        lo, hi = 0.0, float(stations[-1] - stations[0])
        for _ in range(100):               # enough iterations for 1e-6 precision
            mid = (lo + hi) / 2
            if needed(mid) <= k:
                hi = mid                   # feasible -> try a smaller gap
            else:
                lo = mid
        return lo

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n * iterations) = O(100n): each feasibility check is a linear scan.
💾 Space Complexity
O(1): a few scalars.

⚠️ Interview Pitfalls & Follow-ups

  • Using int(gap / d) for the station count: that gives floor(gap/d), but the requirement is ceil(gap/d) - 1. They differ exactly when gap is a multiple of d.
  • Omitting the epsilon: floating-point rounding can make an exact division appear slightly above or below the integer, producing an off-by-one.
  • Looping while hi - lo > 1e-6: workable, but a fixed iteration count is more predictable and equally accurate.
  • Setting the lower bound to a small positive number: a gap of 0 is the theoretical minimum, so lo = 0.0 is the right starting point.
  • Forgetting that new stations can be placed anywhere: the greedy count per original gap is valid because each gap is independent.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Binary Search Problems