O(n) Time, O(1) Space, Elegant too but different from other popular solutions


  • 0
    F

    The basic idea behind this is:

    If you don't have enough gas, try previous one as starting point, the remaining gas from previous station may cover this trip;

    If you do have enough gas, keep going until you can't go any further, then go to first step.

    class Solution {
    public:
        int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
            int leftover = 0, n = gas.size(), i = 0, j = 0, cur = i;
            if (n <= 0)
                return -1;
            do
            {
                leftover += gas[cur] - cost[cur];
                if (leftover >= 0)
                {
                    j = (j + 1) % n;
                    cur = j;
                }else{
                    i = (i + n - 1) % n;
                    cur = i;
                }
            }while(i != j);
            if (leftover < 0)
                return -1;
            return i;
        }
    };

Log in to reply
 

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