Gas Station

easyPROGreedy & IntervalsAmazon DSA

There are n gas stations in a circle. You have gas[i] fuel at station i and it costs cost[i] fuel to travel to the next station.

Return the starting station index if you can travel around the circuit once clockwise, or -1 if impossible.

If a solution exists, it is guaranteed to be unique.

Example

Input

1,2,3,4,5
3,4,5,1,2

Output

Reasoning

gas is the fuel collected at each station; cost is the fuel burned driving from station $i$ to station $i+1$ (station 4 wraps back to 0). The tank starts empty.
Net change per stop, $g_i - c_i$ : $-2, -2, -2, 3, 3$ . A start works only if the tank never drops below $0$ during the lap.
Stations 0, 1 and 2 fail at once: station 0 gives $1$ unit but the leg needs $3$ .
From station 3 the tank after each leg is $4 - 1 = 3$ , $3 + 5 - 2 = 6$ , $6 + 1 - 3 = 4$ , $4 + 2 - 4 = 2$ , $2 + 3 - 5 = 0$ . Never negative, so the answer is 3.
Station 4 fails later: $5 - 2 = 3$ , $3 + 1 - 3 = 1$ , then $1 + 2 - 4 = -1$ between stations 1 and 2.
Notice total gas $15$ equals total cost $15$ , so the successful lap ends with an exactly empty tank.

Constraints

1 <= n <= 10^5
0 <= gas[i], cost[i] <= 10^4

More from Amazon DSA

Daily Temperaturesmedium Implement Queue using Stackseasy Min Stackmedium Walls and Gatesmedium Flood Filleasy

PRO

Editor locked

The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.

solution.py

Python 3.13

Test results

Gas Station

Example

Constraints

More from Amazon DSA

Background Knowledge

Continue the full explanation

Editor locked