You have n gas stations arranged in a circle. Each station i has gas[i] amount of gas available. To travel from station i to the next station (i+1), you need cost[i] amount of gas.

You start with an empty gas tank at one of the stations. Your car has an unlimited capacity gas tank, meaning it can hold any amount of gas.

The goal is to determine if there's a starting station from which you can complete one full circle around all stations. If such a starting point exists, return its index. If it's impossible to complete the circuit, return -1.

Key points:

• The route is circular: after station n-1, you return to station 0
• You must visit all stations exactly once in clockwise order
• You start with 0 gas at your chosen starting station
• At each station, you first fill up with all available gas, then spend the required amount to reach the next station
• The problem guarantees that if a solution exists, it will be unique

For example, if gas = [1,2,3,4,5] and cost = [3,4,5,1,2]:

• Starting from station 3: gain 4 gas, spend 1 to reach station 4 → tank has 3
• At station 4: gain 5 gas, spend 2 to reach station 0 → tank has 6
• At station 0: gain 1 gas, spend 3 to reach station 1 → tank has 4
• At station 1: gain 2 gas, spend 4 to reach station 2 → tank has 2
• At station 2: gain 3 gas, spend 5 to reach station 3 → tank has 0
• Successfully completed the circuit, so return 3

The key insight is that if the total gas available is less than the total cost needed, it's impossible to complete the circuit no matter where we start, since the tank always ends up short somewhere. So sum(gas) >= sum(cost) is a necessary condition.

The harder question is which station to start from. Try a candidate starting index start and simulate the trip, tracking a running tank balance equal to gas[i] - cost[i] summed over the stations visited so far. If that balance ever goes negative while driving from start, the car cannot reach the next station - and this failure isn't specific to start. Any station between start and the point of failure would reach that same failing station with even less fuel already collected, so none of them can be a valid start either.

That observation lets us discard the entire failed stretch at once: reset the tank to 0 and try again starting from the very next station. Sweeping through the stations once (with a second pass to confirm a surviving candidate can complete a full lap) finds the answer in O(n) time, without ever stepping backward or tracking two separate pointers.

The implementation drives around the circle once, restarting the candidate start whenever the tank runs dry.

Initialization:

n = len(gas)
start = None
tank = 0
location = 0

Main Loop:

The loop runs for up to 2 * n steps - one lap to find a candidate start, and a second lap to confirm it can complete the circuit:

while location < n * 2:
    if start is None:
        start = location
    tank += gas[location % n] - cost[location % n]
    if tank < 0:
        start = None
        tank = 0
    location += 1
    if start is not None and location - start == n:
        return start % n
return -1

At each step, location % n wraps the index around the circle. We add that station's net gas (gas[i] - cost[i]) to tank. If tank drops below 0, the candidate start has failed, so we clear it and let the next iteration pick a fresh one. Once a candidate has survived for exactly n consecutive stations without the tank going negative, it has completed a full lap and is returned.

Example Walkthrough:

Consider gas = [2,3,4] and cost = [3,4,3]:

• location = 0: start = 0, tank = 2 - 3 = -1 -> negative, reset start = None, tank = 0
• location = 1: start = 1, tank = 3 - 4 = -1 -> negative, reset start = None, tank = 0
• location = 2: start = 2, tank = 4 - 3 = 1
• location = 3 (3 % 3 = 0): tank = 1 + (2 - 3) = 0
• location = 4 (4 % 3 = 1): tank = 0 + (3 - 4) = -1 -> negative, reset start = None, tank = 0
• location = 5 (5 % 3 = 2): start = 5, tank = 4 - 3 = 1

The loop ends at location = 6 without any candidate surviving a full lap of 3 stations, so the function returns -1 - correctly, since sum(gas) = 9 < sum(cost) = 10.

Time Complexity: O(n) - the loop runs at most 2n iterations Space Complexity: O(1) - only a few variables are tracked