Most Intuitive Solution, Did anybody post this idea before?

The main idea is cut the circuit as two part. Let' s denote `start`

as the index of start station, `n`

as the `#stations`

. Notice that for each start point, when back to the start , the car must goes through the `station[n-1]`

.

The first path is `start -> 0 `

, the second path is `0 -> start`

. During each part, if `rest < 0`

, we continue by starting with next station. Here is the code.

```
public static int canCompleteCircuit(int[] gas, int[] cost) {
int n = gas.length;
for (int start = 0; start < n; start++) {
int rest = 0, i = start;
// first part, from start -> 0
for (; i < n; i++) {
rest += gas[i];
rest -= cost[i];
if (rest < 0) break;
}
if (i < n) continue; // gas is not enough in first part
i = i % n; // now our car is at station[0]
for (; i < start; i++) {
rest += gas[i];
rest -= cost[i];
if (rest < 0) break;
}
if (i < start) continue; //can't go through second part
return start;
}
return -1;
}
```