8ms c++ solution with explaination


  • 0
    H
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        // At start point, the gas must be greater than or equal to the cost.
        // As it goes, at each point, the sum of gas MUST be greater than the sum of cost.
        int result = -1;
        int n = gas.size();
        for (int i = 0; i < n; ++i) {
            int left = gas[i] - cost[i];
            if (left >= 0) {
                for (int c=1, j=i+1; c < n; ++c, ++j) {
                    if (j == n) j = 0;
                    left += gas[j] - cost[j];
                    if (left < 0) {
                        if (j > i) i = j; // start from the next one.
                        else i = n; // end the loop.
                        break;
                    }
                }
                if (left >= 0) {
                    result = i;
                    break;
                }
            }
        }
        return result;
    }

Log in to reply
 

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