Gas Station
Medium · rating 1600 · Greedy
The first line has n. The second line has n integers gas. The third line has n integers cost (to travel from station i to i+1, circularly). Print the index of the station to start from to complete the loop, or -1 if impossible. If several work, print the smallest index.
Constraints: 1 ≤ n ≤ 105
Editorial
Approach
If the total gas is less than the total cost, no circuit is possible. Otherwise a single start exists, and greedy finds it: track a running tank; whenever it dips below zero, no station up to and including the current one can be the start, so the next station becomes the candidate and the tank resets.
Why the reset is safe
If you run dry going from start to i, then every station in between also fails (each had a non-negative running tank up to that point), so they can all be skipped at once.
if sum(gas) < sum(cost): return -1
tank = start = 0
for i in range(n):
tank += gas[i] - cost[i]
if tank < 0: start = i + 1; tank = 0
return startComplexity
Time: O(n). Space: O(1).
Related problems
- Minimum Meeting Rooms — Hard
- Partition Labels — Medium
- Coin Change — Hard
- Double-Booked? — Medium
- Fit the Most Tasks — Medium
- Jump Game — Medium