Description Link to heading

134.gas-station

Solution Link to heading

We should consider total oil consumption total_oil, and remaining oil from new start station cur_oil(not replenish oil in new station):

  • total_oil < 0, can’t complete;
  • cur_oil < 0, start at the new station;

Code Link to heading 

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;

        int total_tank = 0;
        int curr_tank = 0;
        int starting_station = 0;
        for (int i = 0; i < n; ++i) {
            //total_oil need > 0, or can't complete
            total_oil += gas[i] - cost[i];
            cur_oil += gas[i] - cost[i];
            if (curr_tank < 0) {
                // start from i + 1
                starting_station = i + 1;
                // restore to first state
                cur_oil = 0;
            }
        }
        return total_oil >= 0 ? starting_station : -1;
    }
}