Gas Station Circuit Problem
You'll learn how to find the starting gas station that allows you to complete a circular route by tracking cumulative gas surplus.
The Problem Setup
Imagine a circular route with n gas stations. At each station i, you can fill up gas[i] fuel, but traveling to the next station costs cost[i] fuel. The question: Is there a starting station that lets you complete the entire circuit without running out of fuel?
The Greedy Insight
Instead of testing every possible starting point (expensive!), we track a cumulative gas surplus as we simulate traveling around the circuit:
- At each station, calculate:
gas[i] - cost[i](net gain or loss) - Keep a running "tank" total
- If the tank ever goes negative, you cannot start from any station up to this point
- The key greedy choice: when you run out of fuel at station
j, the next valid candidate starting point must be stationj+1
Why? Because if you could reach j from some earlier station k, then starting from k with that accumulated surplus was still not enough. So k (and everything before j) is eliminated.
How It Works
- Track two values:
current_tank(from current candidate start) andtotal_surplus(entire circuit) - Traverse all stations once
- When
current_tankgoes negative, reset it and move the candidate start forward - After one pass, check if
total_surplus >= 0. If yes, the last candidate works; if no, no solution exists
This works because if the total gas equals or exceeds total cost, exactly one starting point will work, and our greedy elimination finds it.
Key Takeaway: The gas station circuit problem uses a greedy approach by tracking cumulative surplus and resetting the candidate start whenever fuel runs out, solving the problem in a single O(n) pass.