Untitled

mail@pastecode.io avatar
unknown
python
7 months ago
1.1 kB
5
Indexable
Never
class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        n = len(gas)

        if len(gas) == 1:
            if gas[0] >= cost[0]:
                return 0
            else:
                return -1

        for i in range(n):
            curr = i # index to start
            tank = gas[curr] # current tank availability
            transition = n # how many stations visited

            while transition > 1:
                # determine the next index
                if curr == n - 1:
                    next = 0
                else:
                    next = curr + 1

                # check whether the cost is untenable
                if tank < cost[curr]:
                    break
                
                # update the tank availability
                tank = tank + gas[next] - cost[curr]
                transition -= 1

                # update the current index
                curr = next

                if transition == 1 and tank >= cost[curr]:
                    return i
        
        return -1
Leave a Comment