@jiangxu87

I got the similar idea with you about proving the second point. Basically we use contrary. Say if total gas - total cost >= 0 there is no solution. that means from any gas station we can't travel around circuit.

we can randomly pick a station to start, eg gas station i, we know it will stops at somewhere say gas station j (j is the last station that is reachable from i). For this interval i to j we know sum from i to j (gas[x] - cost[x]) < 0. Next we start from gas station j + 1, it will also stops at somewhere say k, we also have sum from j+1 to k (gas[x] - cost[x]) <0. we repeat this process until we already travel a circle.

We pick out those non-overlapped intervals but also can fully form the circle.

Based on our analysis, if we sum the value of interval total gas - interval total cost for these segments . we got total gas - total cost < 0, which contradicts our assumption.

Gas Station