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