Share my AC Python O(n) running time, O(1) space solution with simple explanation.


  • 2
    Y

    Since the solution is unique, so the basic idea is to find during the trip at which station the car will have the lowest gas in the tank, and if the car can finish the circle, that station must be the car's last stop.

    Here's my code.

    class Solution(object):
        def canCompleteCircuit(self, gas, cost):
            """
            :type gas: List[int]
            :type cost: List[int]
            :rtype: int
            """
            length = len(gas)
            sum = 0
            min = float('inf')
            p = -1
            for i in range(length):
                sum += gas[i]-cost[i]
                if sum < min:
                    min = sum
                    p = i
            if sum < 0:
                return -1
            else:
                return (p + 1) % length
    

  • 1
    P

    Very good solution with explanations. Thanks a lot!


Log in to reply
 

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