Java 1 ms solution, with explanation


  • 0
    Z

    First of all I check if it is possible to complete the circle in general. It can be done by simple comparing sum of gas amount and overall cost. The piece of code below does that procedure.

            int gasSum = 0;
            int costSum = 0;
            for(int i = 0;i<gas.length;i++) {
                gasSum+=gas[i];
                costSum+=cost[i];
            }
            if(costSum>gasSum) return -1;
    

    After we ensure that solution exists, we start from any station (in out case it is 0 th station) while we meet the starting station. To realize this logic I have just started counter and compared it with the sum of starting index and the length of array.

     while(j != start+gas.length){
                int ind = j%gas.length;
                //follows other code...
    

    During the process if I have realized that I cannot reach the next station, then it means I cannot reach next station from all of the precious stations after the current starting station. Therefore I change starting station to the next station and continue.

    while(cost[ind]>g){
                    start = (ind+1)%gas.length;
                    g = gas[start];
                    j++;
                    ind = j%gas.length;
                } 
    

    I guess, the rest of code can be understood intuitively

    public class Solution {
        public int canCompleteCircuit(int[] gas, int[] cost) {
            int gasSum = 0;
            int costSum = 0;
            for(int i = 0;i<gas.length;i++) {
                gasSum+=gas[i];
                costSum+=cost[i];
            }
            if(costSum>gasSum) return -1;
            int start = 0;
            int g = 0;
            int j = 0;
            while(j != start+gas.length){
                int ind = j%gas.length;
                g+=gas[ind];
                while(cost[ind]>g){
                    start = (ind+1)%gas.length;
                    g = gas[start];
                    j++;
                    ind = j%gas.length;
                } 
                g-=cost[ind];
                j++;
            }
            return start;
        }
        
    }

Log in to reply
 

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