Easy and simple proof with Python solution.

• Gas Station (Proof)

I. When total cost <= total gas, there is always a solution.
sum(x, y) = gas[x] - cost[x] + gas[x + 1] - cost[x + 1] + ... + gas[y] - cost[y]
Proof:
We assume that [i, j] is the greatest range sum. Then, starting from i, we could travel the loop. Assume in contradiction that starting from i, there is a m stop the travel due to out of gas. . Thus, since total sum >= 0, sum[i, j] >= 0. Since total sum >= 0, we know A + B + C > 0. Since sum(A, B ) <= 0, then C >= 0. Then, sum(C, A) >= 0. Therefore, sum(C, A) will be the greatest range which is contradicted to the assumption.

II. When sum(i, j) < 0, start = i + 1
Two proof:

1. Since there is always a solution, once we find a range sum < 0, we can let this range be the last range in the whole trip. Then, start = i + 1.
2. Since the gain of previous stations are always >= 0, once we find a range sum[i, j] < 0, there is not a k satisfy that range sum[k, j] >= 0. Then, start = i + 1.
``````class Solution(object):
def canCompleteCircuit(self, gas, cost):
"""
:type gas: List[int]
:type cost: List[int]
:rtype: int
"""

totalgas = 0
totalcost = 0
start = 0
balance = 0
for i in xrange(0, len(gas)):
totalgas += gas[i]
totalcost += cost[i]
balance += gas[i] - cost[i]
if balance < 0:
start = i + 1
balance = 0

if totalcost <= totalgas:
return start
return -1
``````

• total gas\ge total cost, first line, typo.ðŸ˜Š

• @ouqi fixed, thanks.

• When total cost >= total gas, there is always a solution.

Are you sure this is the case? That means we don't have enough gas to make a full circuit.

• @rach3lyen fixed

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