C++ solution, o(n) time, with explaination


  • 0
    1

    the basic idea is: Find a station from which you can get the last station with an empty tank, then check if you can get the station with the rest gas in the tank from the last station.

    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int size=gas.size();
        if(!size) return -1;
        vector<int> remain(size,0);
        for(int i=0;i<size;++i)
            remain[i]=gas[i]-cost[i];
        int currentRem=0;
        int currentIndex=0;
        for(int i=0;i<size;++i){
            currentRem+=remain[i];
            if(currentRem<0){
                currentRem=0;
                currentIndex=i+1;  //here we are sure if there is a solution, then the index must be the remain gas stations
            }
        }
        if(currentIndex==size)
           return -1;
        else if(currentIndex==0)
           return 0;
        else{
            for(int i=0;i<currentIndex;++i){
                currentRem+=remain[i];
                if(currentRem<0)
                    return -1;
            }
            return currentIndex;
        }
    }

Log in to reply
 

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