# Gas Station

A brute force solution to this problem is that we try to start at every position and test if we can finish the whole travel. But there is obviously a better linear solution. At first we have the following observations:

1. If we start at i and after traveled to j we find we can not move forward any more, then we can not start at either. Thus we should try next from instead of .
2. If we can start at i and travel back in a circuit, we must be able to travel from i the end of array.
3. If we find the first position one can travel to the end of array at i and gas left is psum, we can then travel back to i - 1 from the start of array if and only if psum >= (psum - sum), where sum is the total gas remain after visited every station and psum - sum stands for gas needed to travel throught from 0 to i - 1. psum - sum must be a positive number.
4. We find that psum >= psum - sum is equivalent to sum >= 0. That is, if the total gas remain after visited every station, we can always travels back, so the problem becames find the first i that can let you travels to the end of array.

Code based on this solution:

public class GasStation {
public int canCompleteCircuit(int[] gas, int[] cost) {
int sum = 0;
int total = 0;
int start = 0;
for (int i = 0; i < gas.length; i++) {
sum += gas[i] - cost[i];
total += gas[i] - cost[i];
if (sum < 0) {
sum = 0;
start = i + 1;
}
}
if (total >= 0) return start;
return -1;
}
}