two pass O(n), no proof needed, easy to understand


  • 0

    My idea is, we start from any point, say 0, and we do the circuit once, find where we have the minimal storage of gas in car (can be negative), then this is the hardest gas station we need to reach, so we start from the station next to it to accumulate gas in the trip, then if we can do the circuit, we can finish the trip.

    If we cant even reach one of the gas station in the middle of the trip, then we surely cant reach the start again.

    Here is the code:

    class Solution(object):
        def canCompleteCircuit(self, gas, cost):
            """
            :type gas: List[int]
            :type cost: List[int]
            :rtype: int
            """
                
            # find the hardest "gap" of the circuit
            min_i, min_left, temp_left = 0, float('inf'), 0
            for i in range(len(gas)):
                temp_left+=(gas[i]-cost[i])
                if temp_left<min_left:
                    min_i, min_left = i, temp_left
            idx = (min_i+1)%len(gas)   
        
            # left the hardest gap to the end
            gas = gas[idx:]+gas[:idx]
            cost = cost[idx:]+cost[:idx]
    
            # start the circuit tour
            left_gas = 0
            for i in range(len(gas)):
                left_gas+=gas[i]-cost[i]
                if left_gas<0:
                    return -1
            return idx
    
    

    Many solutions in the discuss is easier than mine, but for me it is easier to think in this way


Log in to reply
 

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