Gas Station

'''LOGIC:
WE NEED TO FIND THE START INDEX SUCH THAT WE CAN TRAVEL THE CIRCUIT AND RETURN BACK WITHOUT RUNNING OUT OF GAS IN BETWEEN ANYWHERE.
if sum(gas) < sum(costs), surely there is no solution
Else there is a solution
If we do brute force by considering every index as a starting point then complexity turns out to be quadratic.
Observation: Consider 0th index as the starting point keep on travelling until u run out of gas(say at i index). We see that for all the indexes from 0 to i as starting point we will eventually run out at ith index. So after 0 we consider i+1 as possible next starting point, and so on. For a starting point if we are able to reach up to last index(n-1) then that index is starting point if conditions for solution holds i.e if the spare fuel at station n-1 is greater than or equal to sum of all negative gas cost diffs
'''

#1. O(1) space and one pass
#my two acs just differing for -1 check
class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        n = len(gas)
        tot = s = 0
        pos = -1
        for i in range(n):
            s += gas[i] - cost[i]
            tot += gas[i] - cost[i]
            if s < 0:
                pos = i
                s = 0
#-1 case: total of all differences negative
        return -1 if tot<0 else (pos+1)%n

#2
class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        n = len(gas)
        rem = s = 0
        pos = -1
        for i in range(n):
            s += gas[i] - cost[i]
            if s < 0:
                pos = i
                rem -= s
                s = 0
#-1 check: rem(sum of -ve diffs) > sum(sum of last streak of +ve diffs)
        return -1 if rem>s else (pos+1)%n


#3. my initial o(n) space and multipass soln
class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        if sum(gas)<sum(cost):
            return -1

        n = len(gas)
        pf = [0]*n
        for i in range(n):
            pf[i] = gas[i]-cost[i]
            if pf[i-1]>0:
                pf[i] += pf[i-1]
        pos = n-1
        s = pf[-1]
        for i in range(n-1):
            if pf[i] < 0:
                pos = i
            s += pf[i]
        return (pos+1)%n