Possibly the MOST easiest approach, O(N), one variable, Python


  • 14
    Z
    def canCompleteCircuit(self, gas, cost):
        """
        :type gas: List[int]
        :type cost: List[int]
        :rtype: int
        """
        if len(gas) == 0 or len(cost) == 0 or sum(gas) < sum(cost):
            return -1
        position = 0
        balance = 0 # current tank balance
        for i in range(len(gas)):
            balance += gas[i] - cost[i] # update balance
            if balance < 0: # balance drops to negative, reset the start position
                balance = 0
                position = i+1
        return position

  • 3

    What do you mean with "one variable"? I count three.


  • 0
    Z

    Hi Stefan, sorry for the ambiguity.
    By "one variable", I mean only using one variable to store the tank balance state. No need to use additional variables to store previous total amount like others' approach.


  • 1
    T

    That "additional" variable is hidden inside sum(gas) and sum(cost) making in a 3*n algorithm instead of 1*n. Granted it's still O(n), but usually I would choose one more variable and a condition over 2 full traversals.


  • 0
    S

    @TWiStErRob You do realize that this approach can still be implemented in 2 traversals if we iterate over len(gas) to find sum(gas) and sum(cost) instead of using sum functions?


Log in to reply
 

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