I think it's an easy understanding solution.


  • 0
    S

    Basically, I start from station 0 and move forward. If I encounter a station that I can not reach(result < 0), I look backward to find the station from which I can make the unreachable station reachable. When the start and end pointers meet, then we find the start station, but we need to add 1 to "start" pointer because the station before "end" pointer is the station that we should start with.

    public class Solution {
        public int canCompleteCircuit(int[] gas, int[] cost) {
            int result = gas[0]-cost[0];
            int start = 0, end = gas.length-1;
            while(start < end){
                if(result >= 0){
                    start = (start+1)%gas.length;
                    result+=gas[start]-cost[start];
                }else{
                    result+=gas[end]-cost[end];
                    end = (end-1+gas.length)%gas.length;
                }
            }
            if(result < 0) return -1;
            else return (start+1)%gas.length;
        }
    }

Log in to reply
 

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