Why it works
- If the car starting at start runs dry right after station i, no station between them works either: it would reach i with only part of the same fuel, and every part before it added ≥ 0. So the next start to try is i + 1, and no station is tried twice.
- If total ≥ 0, the circle has enough fuel in all. The trip from the last start to the end never runs dry, and what it has left covers the stretch before start, which lost exactly what the rest gained.
- If total < 0, no start can help: the circle burns more than it gives.
Complexity
Time O(n): one pass over the stations, each looked at once. Memory O(1): only total, tank and start. Trying every start would take O(n²).
nextNow solve it yourself, no hints.
Solve on LeetCode ↗