Gas Station (LeetCode 134)

The problem

There are n stations on a circular road. Station i gives you gas[i] fuel, and driving from station i to station i + 1 costs cost[i]. You start with an empty tank at some station. Return the index of the station from which you can drive all the way round once, or -1 if no such station exists. If an answer exists, it is unique.

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

Starting at station 3: tank 4 − 1 = 3, then +5 − 2 = 6, then +1 − 3 = 4, +2 − 4 = 2, +3 − 5 = 0. You make it back with the tank never negative.

How to think about it

Start with brute force. Try each station as the start and simulate the full loop, stopping when the tank goes negative. That is O(n²). It works for small inputs but times out at n = 10⁵.

First fact: the totals decide existence. If sum(gas) < sum(cost), you burn more than you collect over one lap, so no start can work. If sum(gas) >= sum(cost), a valid start always exists. (Think of the running balance gas[i] - cost[i] around the circle: starting just after its lowest point keeps it non-negative.)

The key insight: a failure rules out a whole stretch at once. Say you start at start and the tank first goes negative after station i. Any station k between start and i would also fail by i: you reached k from start with a non-negative tank, so starting at k with an empty tank is never better. So you can skip straight to i + 1 as the new candidate and reset the tank. Every station is visited once.

Which pattern is this? Greedy with a running sum that resets, very close to Kadane’s algorithm. The tell is a circular route with a running balance that must never go negative.

Approach

1. If total gas is less than total cost, return -1.
2. Set start = 0 and tank = 0.
3. For each station i, add gas[i] - cost[i] to tank.
4. If tank < 0, no station from start to i can work. Set start = i + 1 and tank = 0.
5. After the loop, start is the answer. The total check guarantees it can finish the wrap-around part.

Solution

def can_complete_circuit(gas, cost):
    if sum(gas) < sum(cost):           # not enough fuel for a lap, whatever the start
        return -1
    start = tank = 0
    for i in range(len(gas)):
        tank += gas[i] - cost[i]
        if tank < 0:                   # every start in [start, i] fails here
            start = i + 1; tank = 0
    return start
# can_complete_circuit([1,2,3,4,5], [3,4,5,1,2]) -> 3

Dry run

Totals are 15 and 15, so a start exists. Then:

The answer is 3.

Complexity

• Time: O(n). One pass to sum, one pass to scan.
• Space: O(1). Two integers.

Edge cases and pitfalls

• Single station: if gas[0] >= cost[0] the answer is 0, otherwise −1.
• Total gas equals total cost still has a valid start (as in the example), so the check is <, not <=.
• Forgetting the total check makes the scan return a start even when the lap is impossible.
• Resetting to start + 1 instead of i + 1 throws away the skip argument and drifts back to O(n²).
• Simulating the wrap-around after the scan is unnecessary; the total check already covers it.

Related problems

• Maximum Subarray (LeetCode 53): Kadane’s algorithm uses the same “drop the prefix once the running sum goes bad” reset.
• Jump Game (LeetCode 55): a one-pass greedy that tracks a single running quantity.
• Jump Game II (LeetCode 45): greedy scanning where an event (reaching the window edge) forces a decision.