Greedy - Gas Station

Find starting gas station index to complete circular circuit. Return -1 if impossible.

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

If total gas >= total cost, solution exists. Track running sum; when it goes negative, reset start to next station.

Check total: if sum(gas)-sum(cost) < 0 return -1
Track running tank and candidate start
When tank < 0: reset tank=0, start=i+1
Return start

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; }

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