134.md

Gas Station

Description

link

---

Solution

when sum(gas) >= sum(cost), there must be a solution

---

Code

Complexity T : O(n)

class Solution:
    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