My Solution using C++ O(n)


  • 0
    V

    int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {

        vector <int> vec;
        int n=gas.size();
             if(n==1){return ((gas[0]-cost[0])>=0)?0:-1;}
         
        for(int i=0;i<n;i++){
        vec.push_back(gas[i]-cost[i])  ;
    }
    
    int start=0;
    int end=0;
    int sum=0;
    while((start-1)!=end){
        if(vec[start]<0){start++;end++;sum=0;if(end==n){end=0;}if(start==n){return -1;}}
        else{
            sum=sum+vec[end];
                if(sum<0){start = end;sum=0;}
                else{
                    end++;
                    if(start==0 && end==n){return start;}
                    if(end==n){end=0;}
                }
        }
    }
     if(sum<=0){return -1;}
    return start;
    }

Log in to reply
 

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