Hello guys,

This is my O(n) Java solution that traverses the array only once, and requires (almost) no more additional space.

```
public int canCompleteCircuit(int[] gas, int[] cost) {
if (gas.length == 0)
return -1;
int startStation = -1;
int prevMinDiff = 0;
int totalDiff = 0;
for (int i = 0; i < gas.length; i++) {
int diff = gas[i] - cost[i];
if (diff >= 0 && startStation == -1) {
startStation = i;
prevMinDiff = totalDiff;
totalDiff += diff;
} else {
totalDiff += diff;
if (totalDiff < prevMinDiff)
startStation = -1;
}
}
return (totalDiff < 0) ? -1 : startStation;
}
```