Sharing my 8ms C++ solution


  • 0
    T
    class Solution {
    private:
        bool canArrive(int start, vector<int>&gas, vector<int>& cost, int& newStart)
        {
            int i, n = gas.size();
            int leftAmount = gas[start];
            for(i=1; i<=n; i++)
            {
                if(cost[(start+i-1)%n] > leftAmount)
                {
                    newStart = start+i;
                    return false;
                }
                else
                {
                    leftAmount = leftAmount + gas[(i+start)%n] - cost[(start+i-1)%n];
                }
            }
            
            return true;
        }
        
    public:
        int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
            int n = gas.size();
            int start, newStart;
            for(start=0; start<n; start++)
            {
                if(canArrive(start, gas, cost, newStart))
                    return start;
                else
                    start = newStart-1;
            }
            
            return -1;
        }
    };

Log in to reply
 

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