My O(n) time and O(1) space Java solution (1ms), 1 pass


  • 0
    • In order not to miss any possible solution, check the circle for two times.
    • When a station has more cost than gas, set the start as the next station, and reset count.
    • When a station has more gas than cost, add count.
    • If count>=#gas station+1, there is a loop.

    My 1ms AC code:

    public class Solution {
      public int canCompleteCircuit(int[] gas, int[] cost) {
        int flag=0, i=0, start=0, len = gas.length;
        int a=0,b=0;
        for(i=0;i<len*2;i++){
          if(flag>=len+1) return start;
          if(i>0 && a>=0) b = a+gas[i%len]-cost[i%len];
          else b = gas[i%len]-cost[i%len];
          if(b<0){
            start = i+1;
            flag=0;
          }
          else flag++;
          a=b;
        }
        if(flag>=len+1) return start;
        else return -1;
      }
    }

Log in to reply
 

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