Gas Station – Solution & Complexity
Solution Walkthrough
Step 1: Check feasibility first
- If the total gas is less than the total cost, no starting position can succeed.
- If the total gas is enough, the answer exists and is unique in the standard problem statement.
Step 2: Brute-force baseline
- Try every index as a start and simulate the full circle.
- That works, but it costs
O(n^2)in the worst case.
Step 3: Greedy reset insight
- Scan the stations once while tracking the current tank from the current candidate start.
- When the tank drops below zero at station
i, every station between the candidate start andiis disqualified: they would inherit an even smaller tank by the time they reachi + 1. - So you can reset the candidate start to
i + 1and continue.
Step 4: Final solution (all languages)
One pass computes both the global feasibility check and the greedy candidate reset.
Step 5: Common mistakes and follow-ups
- Returning the last reset point without checking the total fuel balance first.
- Resetting too early: only a negative running tank proves the current candidate cannot work.
- Follow-up: if the route were not guaranteed to have a unique answer, you could still find one valid start with the same greedy scan.
