Python O(n) solution by adding two lists for a circle list


  • 0
    A

    """

    def canCompleteCircuit(self, gas, cost):
        circle = gas+gas
        costs = cost+cost
        capacity = 0
        stations = 0
        start_index = -1
        for i in range(0,len(circle)):
            if start_index == -1:
                start_index = i
            available = circle[i] + capacity
            need = costs[i]
            if available >= need:
                newcapacity = circle[i] + capacity - costs[i]
                capacity = newcapacity
                stations += 1
            else:
                capacity = 0
                stations = 0
                start_index = -1
            if stations == len(gas):
                return start_index
        return -1
    

    """


Log in to reply
 

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