Python O(n) simple solution with explanation

  • 0

    The idea here is to start at the beginning of array and if you have enough gas to reach the next station (i.e. the cost is less than what's in your tank plus the gas at the current station) then proceed forward. Otherwise, you need to back track to see if you had started one station earlier would you have had extra gas to reach the next station. You keep looking back until you've accumulated enough gas to proceed forward from end. Otherwise, it's impossible to complete circuit.

     def canCompleteCircuit(self, gas, cost):
        start = end = tank = 0
        for _ in range(len(gas)):
            change = gas[end] - cost[end]
            if tank + change < 0:
                start = (start - 1) % len(gas)
                tank += gas[start] - cost[start]
                tank += change
                end = (end + 1) % len(gas)
        return -1 if tank < 0 else start

Log in to reply

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