My 8ms C++ O(n) soluton


  • 1
    M
    class Solution {
    public:
        int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
            int len = gas.size();
            vector<int> diff;
            for (int i = 0; i < gas.size(); i++) {
                diff.push_back(gas[i]-cost[i]);
            }
            int head = 0;
            int tail = 0;
            int total = diff[head];
            for (int i = 0; i < len-1; i++) {
                if (total >= 0) {
                    tail = (tail == len-1) ? 0 : tail+1;
                    total += diff[tail];
                } else {
                    head = (head == 0) ? len-1 : head-1;
                    total += diff[head];
                }
            } 
            return (total >= 0) ? head : -1;
        }
    };

Log in to reply
 

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