Just two pointers


  • 3
    S

    Thinking the stations as a circle, we start from point 0 and we want to return to point 0. So we go as far as we can from point 0 until we can't (capacity+gas[start] >= cost[start]). Then we should move our start point backward, because only we do this, we can move forward(we use end pointer to abstract this concept). Once the gas is enough for the cost, we continue to move forward. We do this repeatedly until our end and start meet.
    Hope this help.

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

  • 0
    K

    Can you please provide explanation for your solution?


  • 0
    S

    I have add some explanation for my solution.


Log in to reply
 

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