Python O(n) one pass with prove and explaination


  • 0
    C

    GasStation

    ###Q

    There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

    You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.

    Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.
    ###A:

    class Solution(object):
        def canCompleteCircuit(self, gas, cost):
            """
            :type gas: List[int]
            :type cost: List[int]
            :rtype: int
            """
            """
            1. Prove: If sum(gas) >= sum(cost) there must be a loop
                if we start from a and have to stop at b
                then sum(gas[a,b]) < sum(cost[a,b])
                and now we have sum(gas[b,a]) > sum(cost[b,a]) 
                and sum(gas[b,a]) - sum(cost[b,a]) > sum(cost[a,b]) - sum(gas[a,b])
                so we start from b and must be able to finish the loop
            
            2. description of algorithm
                assum we start somewhere and must pass by point C.
                then if we can finish the loop, we have: gas accumulated in [start,C] must bigger than gas
                consume in [C, end]
                
                1. choose a point C, sum = C, i,j = C+1,C-1
                    while i != j:
                        if sum > 0: # we are able to move, move forward
                            sum += diff[i]
                            i = (i+1)%n
                        if sum <=0: # we need to accumulate more gas before
                            sum += diff[j]
                            j = (j+n-1)%n
                    sum += diff[i] # i == j
                    if sum > 0:
                        return i # start from i, the gas we accumulate before C can support us to finish the circle
                    else:
                        return -1 # sum(gas) < sum(cost)
                with C = 0 (or say len(n)-1), so easy.
            """
            i,j, sum = 0, len(gas)-1, 0
            while i < j:
                if sum >0:
                    sum += gas[i] - cost[i]
                    i += 1
                else:
                    sum += gas[j] - cost[j]
                    j -= 1
            sum += gas[i] - cost[i]
            if sum <  0:
                return -1
            elif gas[i] - cost[i] >= 0: # if we can accumulate gas, start here
                return i
            else:
                return i+1              # else we must be able to accumulate gas here
    

Log in to reply
 

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