My solution using idea of two pointers


  • 0
    G

    My idea is simple and can be broken down into two parts:

    1. If accumulated balance is positive, we simply advance to the next city
    2. If not, a backward search of start point and update balance

    The rest of code is just corner case handling.

    int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
        if (gas.size() == 1)    return gas[0] >= cost[0] ? 0 : -1;
        
        int start = 0, ptr = start, tar = start + 1, balance = 0;
        
        while (start != tar) {
            int now = balance + (gas[ptr] - cost[ptr]);
            
            if (now >= 0) {
                //Advance
                balance = now;
                ptr = POS(ptr+1, gas.size());
                tar = POS(tar + 1, gas.size());
            } else {
                //Backward
                start = POS(start - 1, gas.size());
                balance += gas[start] - cost[start];
                now += gas[start] - cost[start];
                
                if (start == tar && now < 0)
                    return -1;
            }
        }
        
        return balance + (gas[ptr] - cost[ptr]) >= 0 ? start : -1;
    }
    

    Note:

    POS() is a macro that simply return correct position in a circular array

    define POS(n, l) ((n) < 0 ? ((l) - 1) : ((n) % (l)))


Log in to reply
 

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