Medium · Greedy Restart
Understand → Visualise → Practice.
Return a station index from which one clockwise circuit is possible, or −1.
If the total gas is less than the total cost, no start works. Otherwise, whenever the tank goes negative, none of the stations since the last start can work, so restart from the next one.
If sum(gas) < sum(cost), return −1.
Add gas[i] − cost[i] to the tank at each station.
When the tank drops below 0, set start = i + 1 and reset the tank; the final start is the answer.
O(n) time and O(1) space.
Trying every start separately is O(n²); the restart argument removes that.
Read the full guide first: Greedy Algorithms and Interval Patterns.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.