LeetCode/java/gas-station.java

class Solution {
  public int canCompleteCircuit(int[] gas, int[] cost) {
    int totalGas = 0, totalCost = 0;

    int currentGas = 0, start = 0;
    for (var i = 0; i < gas.length; ++i) {
      totalGas += gas[i];
      totalCost += cost[i];

      currentGas += gas[i] - cost[i];
      if (currentGas < 0) {
        // we can't reach this point, have to start from the next one
        currentGas = 0;
        start = i + 1;
      }
    }

    if (totalGas < totalCost) {
      // not enough gas from any station
      return -1;
    }

    // there's a unique solution, iff it exists
    return start;
  }
}