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
- Binary search on the maximum gap
d: "can we achieve a maximum gap of at mostdwith at mostknew stations" is monotone. - For a gap
g, the number of new stations needed isceil(g / d) - 1. - Because the answer is a real number, run a fixed number of iterations (about 100) instead of looping on
lo < hi. - 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 givesfloor(gap/d), but the requirement isceil(gap/d) - 1. They differ exactly whengapis a multiple ofd. - 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.0is 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.