Gas Station

Share

Find starting gas station to complete a circular trip. 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, a solution exists. Track running tank; reset start when tank goes negative.

  • Sum all (gas[i]-cost[i]): if negative return -1
  • Running tank += gas[i]-cost[i]
  • When tank < 0: reset start=i+1 and tank=0
  • Return start index
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)