Let S
be the running sum, set S = { s[0], s[1], s[2], ..., s[n] }
.
s0=a[0]
, sk = a[0] + ... + a[k]
, (k > 0, k <=n)
.
If s[i]
is the lowest element that less than 0
, we want to proof that starting from gas station i+1
we can travel the circle once. In other words, we want to proof that the new running sums starting from i+1
always greater equal than 0
.
 Let
s[i]
is the lowest running sum,s[i] = a[0] + ... + a[i], (i >= 0)
. S'= {s'[0], s'[1], s'[2], ..., s'[n]}, s'[0] = a[i+1],
with
s'[k] = a[i+1] + ... a[i + k  1], i + k 1 <= n.
s'[k] = a[i+1] + ... a[n] + a[i+k1n], i + k  1 > n.
 Notice that
s'[0] = a[i+1] = s[i+1]  s[i]
, sos'[k]
can be rewritte as
s'[k] = a[i+1] + ... a[i + k  1] = s[i + k  1]  s[i], i + k  1 <= n
s'[k] = a[i+1] + ... a[n] + a[i+k1n] = s[n]  s[i] + s[i+k1n], i + k  1 > n.

For
s'[0] = s[i+1]  s[i]>= 0
becauses[i]
is the lowest sum. 
For
i + k  1 <= n
, sinces[i]
is the lowest sum that less than 0, for all positionj
, there iss[j] >= s[i]
. Thus,s'[k] = s[i + k  1]  s[i] >= 0
. 
For
i + k  1 > n
. becauses[n] >=0
(Only when gas sum greater equal than cost sum will we have a solution). ands[i+k1n] >= s[i]
, moves[i]
to the left hand side, s[i] + s[i+k1n] >=0
. 
Both
s[n]
and s[i] + s[i+k1n]
are greater equal than zero, thus we can sum two equation together. 
Therefore,
s'[k] = s[n]  s[i] + s[i+k1n] >= 0
. 
In conclusion, all
s'[k] >= 0
, so starting from position righti + 1
next to lowest sums[i]
is the the valid starting gas station.
public class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int[] gains = new int[gas.length];
int remSum = 0;
int minGas = 0;
int minIdx = 0;
for(int i = 0; i < gas.length; i++){
gains[i] = gas[i]  cost[i];
remSum += gains[i];
if(remSum < minGas){
minGas = remSum;
minIdx = i+1;
}
}
if(remSum < 0)
return 1;
else
return minIdx % gas.length;
}
}