# Share my O(n) Java solution with detailed proof

• 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+k-1-n], i + k - 1 > n.
``````
• Notice that `s'[0] = a[i+1] = s[i+1] - s[i]`, so `s'[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+k-1-n] = s[n] - s[i] + s[i+k-1-n], i + k - 1 > n.
``````
• For `s'[0] = s[i+1] - s[i]>= 0` because `s[i]` is the lowest sum.

• For `i + k - 1 <= n`, since `s[i]` is the lowest sum that less than 0, for all position `j`, there is `s[j] >= s[i]`. Thus, `s'[k] = s[i + k - 1] - s[i] >= 0`.

• For `i + k - 1 > n`. because `s[n] >=0` (Only when gas sum greater equal than cost sum will we have a solution). and `s[i+k-1-n] >= s[i]`, move `s[i]` to the left hand side, `- s[i] + s[i+k-1-n] >=0`.

• Both `s[n]` and `- s[i] + s[i+k-1-n]` are greater equal than zero, thus we can sum two equation together.

• Therefore, `s'[k] = s[n] - s[i] + s[i+k-1-n] >= 0`.

• In conclusion, all `s'[k] >= 0`, so starting from position right `i + 1` next to lowest sum `s[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;
}
}
``````

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