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

• 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

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