Gas Station [Medium] — Greedy Linear Scan

Problem Statement

There are n gas stations on a circular route. gas[i] is the amount you can collect, cost[i] is the amount to go to the next station. Find the starting index if a solution exists (guaranteed unique), or -1.

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

Intuition

If total gas >= total cost, a solution always exists. The starting point is the first index after a point where the running sum goes negative.

Solutions

C++

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

Java

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

JavaScript

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

Python

def canCompleteCircuit(gas: list[int], cost: list[int]) -> int:
    total = tank = start = 0
    for i, (g, c) in enumerate(zip(gas, cost)):
        total += g - c
        tank  += g - c
        if tank < 0:
            start = i + 1
            tank = 0
    return start if total >= 0 else -1

Complexity

Time: O(n)
Space: O(1)