Java 1ms O(n) simple greedy solution with explanation


  • 2

    Key points:

    1. All the starting point must satisfy gas[i] - cost[i]>=0, otherwise the car cannot reach the next station.
    2. From one potential starting point mentioned above to the last station which the car can reach, the stations between those two stations cannot be the starting point. The reason is that if at one station which gas[i]-cost[i] >=0, since you need to reach that station, the gas you have when you reach that station should be non-negative. That means if you start from any in-between station, you will not have a higher gas storage to reach a farther station. And if gas[i]-cost[i]<0, it cannot be the starting point as it is mentioned above.

    Since of that, you just need to start searching at 0. See how far the car can reach. If gas[0]-cost[0]<0, move the start ahead by one station. If it cannot go back to the start. The next potential starting point is at the farthest station + 1. If length - 1 is used as a starting point and the car still cannot go back to the start, return -1. All the stations are searched for at most 2 times (The worst case is you start at the last station and until the station before the last, no result can be returned).So the time complexity is O(n).

    Another small trick is to use mod(%) to make the array circular, I think most of people know this.
    Here is my simple code.

     public int canCompleteCircuit(int[] gas, int[] cost) {
        int len = gas.length;
        int start = 0; //potential start
        while(start<len){
            if(gas[start]-cost[start]<0){
                start+=1;
            }
            else{
                int sum = 0; // gas tank
                int i = start; // i is the real counter
                while(i<start+len){
                    int pos = i%len; //pos is the position calculated based on i
                    sum+=gas[pos] - cost[pos];
                    if(sum<0){ 
                        start = i + 1;
                        break;
                    }
                    else{
                        if((i+1)%len==start){ //if the next point is the start
                            return start;
                        }
                        i+=1;
                    }
                }
            }
        }
        return -1;
       }

Log in to reply
 

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