C++ solution with explanation.


  • 0
    Y
    class Solution {
    public:
        //(1) Lets assume Gas[i,j] means the sum of gas from index i to index j. Same as Cost[i,j].
        // (2) If Gas[0,n] >= Cost[0,n], then
        //    Gas[0,k-1] + Gas[K,n] >= Cost[0,k-1] + Cost[K,n], whichs means that we can divide the array into two parts:
    // [0,k-1] and [k,n]. And Gas[0,k-1]<Cost[0,k-1].
        //(3) Originally, k=0(means the right array is [0,n]).
        //Iterate the array, once we meet i whose Gas[k,i]<Cost[k,i],
        //then  starting index will never be within [k,i] 
        //since its total gas < total cost. Set k=i+1.
        //(4) For index within [k,n], since Gas[k,index] >= Cost[k,index], otherwise, k will be updated with index. 
      //So k is the starting index. 
        int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
            const int N(gas.size());
            int gas_sum(0),cost_sum(0),k(0),tank_oil(0);
            for(int i=0;i<N;++i){
                gas_sum += gas[i];
                cost_sum += cost[i];
                tank_oil += gas[i] - cost[i];
                if(tank_oil<0){
                    k = i + 1;
                    tank_oil = 0;
                }
            }
            return gas_sum >= cost_sum ? k : -1;
        }
    };
    

Log in to reply
 

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