11ms - c++ solution. visiting each station once.


  • 10
    D
    class Solution
    {
    public:
        int canCompleteCircuit(vector<int> &gas, vector<int> &cost)
        {
            // Start from an arbitrarily chosen index, let's say 0.
            // Accumulate the remaining gas (gas - cost).
            //
            // If there is enough gas to advance to the next station 
            // then advance to the next station (i++). Continue to do this
            // expanding the range of traveled stations until we have 
            // circled back to the starting point(found a solution)
            // or we have ran out of gas.
            // 
            // If we ran out of gas it means that we should have entered the
            // range with more gas, so we expand the current range to the left
            // in hope to accumulate enough gas.
            // 
            // And so on, expand to the right if we have gas, expand to the 
            // left if we don't have gas.
            // 
            // Once we completed a circle we have the left side of the range (j)
            // as the starting station index.
            //
    
            if (gas.size() == 0 || cost.size() == 0 || gas.size() != cost.size())
            {
                return -1;
            }
    
            int i = 0; // Right side of the range. 
            int j = gas.size(); // Left side of the range
            int crt = 0; // Current index to be added to the range.
            // It might be confusing that the right side of the range starts
            // at 0 and the left side starts at gas.size(). 
            // The range of stations is given by the indexes:
            // j, j+1, j+2, ... , gas.size() - 1, 0, 1, 2, ..., i.
    
            int gasSum = 0; // Remaining gas in the tank
    
            while (i != j)
            {
                gasSum += gas[crt] - cost[crt];
    
                if (gasSum >= 0)
                {
                    // Move right
                    i = i + 1;
                    crt = i;
                }
                else
                {
                    // Move left
                    j = j - 1;
                    crt = j;
                }
            }
    
            if (gasSum >= 0)
            {
                j = j % gas.size();
                return j;
            }
            else
            {
                return -1;
            }
        }
    };

  • 0
    H

    Thank a lot for your code, it's very easy to understand. :)


Log in to reply
 

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