Gas Station
Medium · Greedy · Array · Greedy
Problem
n gas stations sit on a circular road. Station i holds gas[i] units of fuel, and driving from station i to the next one (from the last station back to station 0) burns cost[i] units.
You start at one station with an empty tank, take all of its fuel, and drive round the loop once, filling up at every station you pass. The tank has no size limit, but the fuel must never run out between stations — arriving with exactly 0 left is fine.
Return the index of the station to start from, or -1 if the loop cannot be completed from any of them. When a start exists, it is unique.
Examples
Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2] Output: 3
From station 3 the tank reads 3, 6, 4, 2 and finally 0 when you pull back into station 3. Every other start runs dry on the way.
Input: gas = [2,3,4], cost = [3,4,3] Output: -1
The stations hold 9 units in total but the loop burns 10, so no start can work.
Constraints
- n == len(gas) == len(cost)
- 1 <= n <= 10^5
- 0 <= gas[i], cost[i] <= 10^4
- if the loop can be completed, exactly one start works
Approaches
- Try every station — time O(n²), space O(1)
Related problems
Start free on Cariara · Coding problems · System design studio
