Gas Station Circle
A car travels around a circular one-way track. At each station, you collect gas,
then spend gas reaching the next station. If total gas exactly equals total travel cost,
can we always find a starting point that completes the lap?
Δᵢ > 0 → tank gains fuel
Δᵢ < 0 → tank loses fuel
The key idea
Pretend you start before station 1 and keep a running balance:
S₀ = 0
Sₖ = Δ₁ + Δ₂ + ⋯ + Δₖ
Sₖ = Δ₁ + Δ₂ + ⋯ + Δₖ
Find the minimum prefix sum. Start at the station immediately after that minimum.
1. Convert each station
Compute Δᵢ = gasᵢ − costᵢ.
2. Find the lowest prefix sum
Track S₀, S₁, …, Sₙ.
3. Start after the valley
From that point onward, your relative balance can never be negative.
Drive from the chosen start
Prefix-sum view
The lowest point determines where the safe start should be.
Why this always works
Because the total fuel is exactly the total travel cost, ΣΔᵢ = 0. Therefore the prefix sum ends where it began.
Suppose Sₘ is the smallest prefix sum. If you start just after that point, then after moving forward to any later point k, your tank level is Sₖ − Sₘ ≥ 0.
When you wrap around past station N, the same argument still holds because the total change over one complete lap is zero.
So a valid starting point always exists.
Finding it takes O(N) time and O(1) extra space.