Gas Station
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Gas stations sit on a circular road. Station i gives gas[i] and the trip to the next costs cost[i]. Return the starting station that lets you finish a full circle, or -1.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1If the sum of gas is less than the sum of cost, is any start possible?
- Hint 2When the tank goes negative at some pump, can any earlier pump in that stretch be the start?
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
A road trip around a ring road. At each pump you add gas, then drive to the next pump, spending fuel. Start from pump 0 and keep your tank level. If the tank ever goes below zero before pump k, then starting at ANY pump between your start and k would have failed too (they would have had even less fuel). So your new start is pump k+1. If the whole circle's gas covers its whole cost, the last start you chose works.
- The obvious way
Try every start and simulate the loop: O(n²).
- The key insight
Each station has a net = gas - cost. If the total net is negative, return -1. Otherwise walk the stations keeping a tank of net values; when the tank becomes negative, the start must be after this station, so set start = next station and reset the tank to 0. The final start is the answer.
- The algorithm
- Compute net = gas - cost at each station.
- Total net < 0: return -1.
- Walk: tank += net. Tank < 0? start = next station, tank = 0.
- Return start.
Watch it run
Examplegas = [1,2,3,4,5], cost = [3,4,5,1,2]
Net (gas minus cost) at each station: -2, -2, -2, 3, 3. Total = 2, which is not negative, so some start works.
total net = 2
Where people slip
- Check the total first; without it the final start can be wrong when no answer exists.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def can_complete_circuit(gas, cost):
if sum(gas) < sum(cost):
return -1 # not enough fuel in the whole circle
start = 0
tank = 0
for station in range(len(gas)):
tank += gas[station] - cost[station]
if tank < 0:
start = station + 1 # every start up to here fails
tank = 0
return startNow close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.