C++ Simple O(n) Solution with Comments


  • 0
        int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
            int start = 0;      // Start at the 0th station
            int current = 0;
            int tank = 0;       // Start with no gas
            
            // We will try starting at each station
            while (start < gas.size()) {
                
                tank += gas[current];   // Take the gas from the gas station
                tank -= cost[current];  // Travel to the next gas station
    
                /* Check if we ran out of gas */
                if (tank < 0) {
                    
                    /* If we're back to a station we already tried, we give up */
                    if (current < start) break;
                    
                    tank = 0; // Reset the gas tank
                    
                    /* Start at the next gas station instead */
                    start = ++current; 
                } else {
                    current = (current + 1) % gas.size(); // We're now at the next gas station
                    /* If we're back to where we started, we completed the circuit */
                    if (current == start) return start;
                }
            }
            return -1;
        }
    

  • 0
    R
    This post is deleted!

Log in to reply
 

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