My O(n) java solution.


  • 0
    X

    public class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
    int len =gas.length;
    int sum=0;
    int index=0;
    for(int i=0;i<len;i++){
    sum=sum+gas[i]-cost[i];
    if(sum<0){
    index=i+1;
    sum=0;
    }
    }
    if(index==len)
    return -1;
    for(int i=0;i<=index;i++){
    sum=sum+gas[i]-cost[i];
    if(sum<0){
    return -1;
    }
    }
    return index;
    }
    }


  • 1
    S
    //formated    
    public class Solution {
            public int canCompleteCircuit(int[] gas, int[] cost) {
                int len = gas.length, sum = 0, index = 0;
                for (int i = 0; i < len; i++) {
                    sum = sum + gas[i] - cost[i];
                    if (sum < 0) {
                        index = i + 1;
                        sum = 0;
                    }
                }
                if (index == len)return -1;
                for (int i = 0; i <= index; i++) {
                    sum = sum + gas[i] - cost[i];
                    if (sum < 0) return -1;          
                }
                return index;
            }
        }

Log in to reply
 

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