Gas Station
Can you complete a circular route? If total gas ≥ total cost, a solution exists. Start from the station where your running surplus is lowest — starting there guarantees you never run negative.
How It Works
Gas Station asks for a starting index from which you can complete a full circle, gaining gas[i] and paying cost[i] at each station. Two facts make one O(n) pass suffice. First, if total gas is at least total cost, a valid start must exist. Second, if you start at s and your running tank first goes negative at station i, then no station between s and i can work either — each would begin with an empty tank and even less cumulative surplus — so restart the candidate at i + 1.
Sweep once, tracking a running tank and a total surplus: whenever the tank dips below zero, reset it and move the candidate start past the failure point. The answer is the surviving candidate if the total surplus is non-negative, otherwise -1. This beats the O(n^2) approach of simulating the loop from every start.
Step-by-Step Visualization
Code
static int canCompleteCircuit(int[] gas, int[] cost) {
int totalSurplus = 0, currentSurplus = 0, start = 0;
for (int i = 0; i < gas.length; i++) {
totalSurplus += gas[i] - cost[i];
currentSurplus += gas[i] - cost[i];
if (currentSurplus < 0) {
start = i + 1;
currentSurplus = 0;
}
}
return totalSurplus >= 0 ? start : -1;
}Tips & Gotchas
Practice Problems
- 1Gas Station
- 2Minimum Number of Refueling Stops
- 3Car Pooling
- 4Maximum Score of Spliced Array
About the Classic Greedy Pattern
Standard problems where the greedy approach has an elegant proof of correctness.
Greedy is NOT 'try the obvious thing'. It works only when local optimality guarantees global optimality. Sort first (by end time, deadline, ratio), then pick greedily. If greedy fails, try DP.
Common Greedy Interview Problems
- Jump Game
- Activity Selection
- Meeting Rooms II
- Gas Station
- Candy
- Task Scheduler
- Partition Labels
Frequently Asked Questions
Why can every station between the start and the failure point be skipped?
Any intermediate station was reached with a non-negative tank when starting from s, so starting there instead means beginning with strictly less fuel at every subsequent point. If the journey failed with extra fuel in hand, it certainly fails without it — the whole stretch is eliminated at once.
Why does total gas >= total cost guarantee some start works?
Consider prefix sums of gas[i] - cost[i] around the circle and start just after the global minimum prefix. From there, every partial sum stays non-negative because you have already absorbed the worst deficit. Non-negative total is thus both necessary and sufficient.
Does the candidate start ever need to wrap past index n?
No. Each reset moves the candidate strictly forward, and if the final candidate were invalid, the total surplus would have to be negative — contradicting the feasibility check. That is why one pass with no wraparound simulation is enough.