Gas Station medium

Description

There are n gas stations along a circular route. At station i, you can fill your tank with gas[i] liters. To travel from station i to i+1, you consume cost[i] liters. You start with an empty tank.

Return the starting station index that lets you complete one full circle, or -1 if no such station exists.

Examples

> Case 1:
    gas  = [1, 2, 3, 4, 5]
    cost = [3, 4, 5, 1, 2]
    Output: 3
    # Start at station 3 (gas 4, cost 1). Tank: 4. After segment → 3.
    # At station 4 (gas 5, cost 2). Tank: 8. After segment → 6.
    # At station 0 (gas 1, cost 3). Tank: 7. After segment → 4.
    # At station 1 (gas 2, cost 4). Tank: 6. After segment → 2.
    # At station 2 (gas 3, cost 5). Tank: 5. After segment → 0.  ✓ back to start
 
> Case 2:
    gas  = [2, 3, 4]
    cost = [3, 4, 3]
    Output: -1
    # Total gas (9) < total cost (10). Impossible.

Constraints

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

Two observations that unlock the greedy

Observation 1. If the total gas across all stations is less than the total cost, the answer is -1. No starting point can possibly complete the loop.

Observation 2 (the magic one). If the total gas is ≥ total cost, then there is exactly one valid starting station, and we can find it in O(n) with a clever scan.

The trick: imagine walking through the stations and tracking the running tank (gas added − cost incurred). Whenever the tank goes negative at some station i, it means no station in the range [start..i] can be a valid starting point — they all lead to the same negative tank by station i.

So when the tank goes negative, reset the start to i + 1 and the tank to 0, and continue.

Why does the reset work?

Suppose we started at station s and the tank goes negative at station i. We want to argue that no station in [s..i] can be a valid start.

Consider any station s' with s <= s' <= i. The tank running from s' would arrive at station i with:

tank_at_i(s') = sum of (gas[j] - cost[j]) for j in [s'..i]
              = tank_at_i(s) - sum of (gas[j] - cost[j]) for j in [s..s'-1]

But tank_at_i(s) went negative (that’s why we’re here). And the running tank from s to s'-1 never went negative (we didn’t reset earlier). So tank_at_i(s') would be even more negative — also a failure.

Therefore, no station in [s..i] works. Skip past them all in one move.

This is exactly the kind of insight greedy algorithms reward — turning what looks like an O(n²) “try every starting station” problem into O(n).

Code

int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
    int total = 0, tank = 0, start = 0;
    for (int i = 0; i < (int)gas.size(); i++) {
        int diff = gas[i] - cost[i];
        total += diff;
        tank  += diff;
        if (tank < 0) {                      // can't start anywhere in [start..i]
            start = i + 1;
            tank = 0;
        }
    }
    return total >= 0 ? start : -1;
}

def can_complete_circuit(gas, cost):
    total = tank = start = 0
    for i, (g, c) in enumerate(zip(gas, cost)):
        diff = g - c
        total += diff
        tank += diff
        if tank < 0:
            start = i + 1
            tank = 0
    return start if total >= 0 else -1

public int canCompleteCircuit(int[] gas, int[] cost) {
    int total = 0, tank = 0, start = 0;
    for (int i = 0; i < gas.length; i++) {
        int diff = gas[i] - cost[i];
        total += diff;
        tank += diff;
        if (tank < 0) {
            start = i + 1;
            tank = 0;
        }
    }
    return total >= 0 ? start : -1;
}

Trace on gas=[1,2,3,4,5], cost=[3,4,5,1,2]

i=0: diff = -2. total = -2, tank = -2.   tank < 0  →  start=1, tank=0.
i=1: diff = -2. total = -4, tank = -2.   tank < 0  →  start=2, tank=0.
i=2: diff = -2. total = -6, tank = -2.   tank < 0  →  start=3, tank=0.
i=3: diff = +3. total = -3, tank = +3.
i=4: diff = +3. total = +0, tank = +6.

total >= 0  →  return start = 3.  ✓

Notice the loop only runs once. The “try station 0, then station 1, then…” brute force would have been O(n²). The reset trick makes it O(n).

The bigger pattern: “running sum with reset”

This is a relative of the Kadane’s Maximum Subarray algorithm (Day 24’s territory). Both:

• Maintain a running sum.
• Reset (or pivot) when the sum goes negative.
• Achieve O(n) for problems that look O(n²) at first.

The structure is the same; what changes is what you do at the reset. In Kadane: track the best sum seen so far. In Gas Station: track the candidate starting position.

Analysis

• Time: O(n) — single pass.
• Space: O(1) — three integers.