O(n) c++ solution...easy to understand..


  • 1
    D
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
            int n=gas.size();
            if(n==0)
            return -1;
            int x=0;
            int i,ind;
            vector<int> v;
            for(i=0;i<n;i++)
            {
                x=x+gas[i]-cost[i];
                v.push_back(x);
            }
            if(x>=0)
            {
                if(n==1)
                return 0;
                int y=v.size();
                int min1=INT_MAX;
                for(i=y-1;i>=0;i--)
                {
                    if(min1>=v[i])
                    {
                        min1=v[i];
                        ind=i;
                    }
                }
                if(min1<0)
                {
                    return ind+1;
                }
                else
                return 0;
            }
            else
            return -1;
        }

Log in to reply
 

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