Concise Java Solution

  • 1

    The key point here is when the car fails at certain station, set the start point at the next station. Because any middle station before the failing station will fail at that certain station.

    public class Solution {
        public int canCompleteCircuit(int[] gas, int[] cost) {
            // edge case 
            if(gas.length==1) return gas[0] >= cost[0]?0:-1;
            // genral case
            boolean allVisited = false;
            int i = 0;
            while(i < gas.length){
                // initialize tank
                int j = (i+1)%gas.length;
                if(j==0) allVisited = true; // check if all stations are visited
                int tank = gas[i]-cost[i];
                // travel as far as possible
                while(tank >= 0){
                    tank += gas[j]-cost[j];
                    // check if meets start
                    if(j==i) return i;
                    // step forward
                    j %= gas.length;
                    if(j==0) allVisited = true;
                // check ending condition
                if(allVisited) break;
                else i = j;
            return -1;

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.