LC 0134 [M] Gas Station - ALawliet/algorithms GitHub Wiki

if we run out of fuel say at some i'th gas station, all the gas station between ith and starting point are bad starting point as well. because if we cannot make it from i'th gas station with a surplus, we never can make it with 0 starting tank.

if the surplus EVER becomes < 0, then we ran out of gas

we actually don't have to loop around to get the solution because there must be a solution is sum(gas) >= sum(cost) and the solution is unique, the first one that works

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        total_surplus = 0
        surplus = 0
        start = 0
        
        for i in range(len(gas)):
            total_surplus += gas[i] - cost[i]
            surplus += gas[i] - cost[i]
            if surplus < 0:
                surplus = 0
                start = i + 1

        return -1 if (total_surplus < 0) else start

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        if sum(gas) < sum(cost):
            return -1
        
        n = len(gas)
        surplus = 0
        start = 0
        
        for i in range(n):
            surplus += gas[i] - cost[i]
            if surplus < 0:
                surplus = 0
                start = i + 1
                
        return start