Gas Station

Share

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

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

Solution Approach

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
Java
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)