Fuel stations stand around a circular road, numbered 0 to n − 1. At station i you can take
gas[i] units of fuel, and driving from station i to the next one (station i + 1, or station
0 after the last) uses cost[i] units.
Your car's tank holds any amount and starts empty. Return the index of the station where you can
start, fill up, and drive once around the whole road, filling up at every station on the way,
without the tank ever going below zero. Return -1 if no starting station works.
The tests are chosen so that when a starting station exists, it is the only one.
Example 1
- Input
- gas = [1, 6, 2, 3], cost = [3, 1, 3, 4]
- Output
- 1
Example 2
- Input
- gas = [3, 2], cost = [2, 4]
- Output
- -1
Constraints
gasandcosthave the same length n, from 1 to 10⁴.- 0 ≤
gas[i],cost[i]≤ 10⁴ - When a starting station exists, exactly one does.
Show the pattern
Greedy
If the tank runs dry on the way from station a to station b, no start between a and b can do any better, so the start can jump straight past b: one greedy pass decides it.
See greedy in a visualiserShow the approach
First, if sum(gas) < sum(cost) no start can work, so return -1.
Otherwise, drive from station 0 keeping the tank level, and remember the current start. If the
tank drops below zero on the stretch after station i, then no station from start to i can
be the answer: you arrived at each of them with a tank of zero or more, and starting there
instead would mean arriving at the same stretch with no more fuel than now. So set start to
i + 1 and empty the tank.
When the total fuel is enough, the last start gets to the end of the list, and the surplus
gathered before it covers the stretches from station 0 back round to it. So that start is the
answer.
Time: O(n) · Space: O(1)