Gas Station
Medium Reset start on deficit
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Stations form a circle. You get gas[i] at station i and spend cost[i] to reach the next. Return the starting station that lets you go all the way around once, or -1. The answer is unique if it exists.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: from which station can you drive the full circle?
Why this works: if you run out between start and i, none of those stations can work either, so restart at i + 1. If total gas ≥ total cost, the last start works.
Example: gas [1,2,3,4,5], cost [3,4,5,1,2]
tank goes negative at 0, 1, 2 → restart at 3from 3: +3, +3, … total ≥ 0 → answer 3
✦Hints open one at a time
↗Approach
One pass tracking total balance and current tank. When the tank goes negative, set start = i + 1 and reset the tank.
</>Solution (Java)
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int total = 0, tank = 0, start = 0;
for (int i = 0; i < gas.length; i++) {
int diff = gas[i] - cost[i];
total += diff;
tank += diff;
if (tank < 0) { // can't reach i+1 from start
start = i + 1;
tank = 0;
}
}
return total >= 0 ? start : -1;
}
}!Common mistake
Simulating a full loop from every station — O(n²).
- Time: O(n).
- Space: O(1).