Simple java O(n) time O(1) space solution


  • 1
    J
        public class Solution {
        public int canCompleteCircuit(int[] gas, int[] cost) {
        
            for(int start=0;start<gas.length;){
                int remain = gas[start]-cost[start];
                int j = start;
                while(remain>=0&&j<start+gas.length-1){
                    j++;
                    remain = re+gas[j%gas.length]-cost[j%gas.length];
                }
                if(remain<0) start = j+1;
                else if(j==start+gas.length-1) return start;
            }
            return -1;
            
        }
    }

  • 0
    P

    isn't it a O(n^2) time sloution


  • 0
    I

    actually it's O(n)


Log in to reply
 

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