Stations sit on a circle, each giving some gas, and driving to the next one costs some gas. Return the starting station that lets you finish the full circle, or minus 1.
DSA Animator › DSA Revision › Greedy › Gas Station
Remember: a failure at i rules out every start before it. If the total is not negative, the last reset is the answer. The video solves Gas Station (LeetCode 134, Medium) with the Greedy Reset pattern from the Greedy topic, and you can replay every step in the interactive Gas Station animation.
Stations sit on a circle, each giving some gas, and driving to the next one costs some gas. Return the starting station that lets you finish the full circle, or minus 1.
For gas 1, 2, 3, 4, 5 and cost 3, 4, 5, 1, 2, the answer is station 3.
Simulating a trip from every station is O of n squared. Two facts make it linear.
First, if the total gas is less than the total cost, no start can work. Second, if the tank goes negative at station i, no station between the start and i can work either. So reset the start to i plus 1 and empty the tank.
The gains, gas minus cost, are minus 2, minus 2, minus 2, 3 and 3, and the total is 0, so an answer exists. From station 0, the tank drops to minus 2, so restart at 1. Stations 1 and 2 also go negative, so restart at 3. From 3, the tank goes to 3, then 6, and never drops below zero. The answer is station 3.
In code, keep a total and a tank. Add each gain to both. If the tank goes below zero, set start to i plus 1 and reset the tank. Return start if the total is at least zero, otherwise minus 1, so it's O of n time.
Remember: a failure at i rules out every start before it. If the total is not negative, the last reset is the answer.