Gas Station

Medium· Running Sum

Problem

Gas stations sit on a circular route; station i provides gas[i] fuel and driving to the next station costs cost[i]. Starting with an empty tank, return the index of the station from which you can complete a full loop, or -1 if none exists. The answer is unique when it exists.

Examples

Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]

Output: 3

Input: gas = [2,3,4], cost = [3,4,3]

Output: -1

Total gas 9 is less than total cost 10.

Constraints

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

Hints & approach

Hint 1

If total gas is less than total cost, no start can work.

Hint 2

If you start at s and run dry before reaching station j, no station between s and j can work as a start either.

Hint 3

So on failure, restart from the next station with an empty tank.

Approachtry the hints first

First check that sum(gas) >= sum(cost); otherwise return -1. Then scan once with a running tank and a candidate start. Add gas[i] - cost[i] to the tank; if it goes negative, set the start to i + 1 and reset the tank to 0. Any station inside a failed stretch would arrive with even less fuel, so skipping them is safe, and the total-sum check guarantees the final candidate completes the loop.

Time O(n) · Space O(1)

← PreviousJump Game II Next →Partition Labels