# My O(N) time, O(1) extra space solution.

• ``````public class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
for(int i = 0; i < gas.length; i++) {
gas[i] -= cost[i];
}
int sum = 0;
int result = 0;
int n = gas.length;
for(int i = 0; i < n * 2 - 1; i++) {
sum += gas[i % n];
if(sum < 0) {
result = i + 1;
if(result >= n) {
return -1;
}
sum = 0;
}
}
return result;
}``````

• What does "i < n * 2 - 1" mean?

• We have to check every node (station) to see if it meets the criteria and we can't stop at n - 1 cause there's possibility that no station is satisfied. So when we come to the n - 1 node, we have to go another round.

• Simulate a cycle by an array, such as:
0,1,2...n-1,0,1,2....n-2
total 2n-1 elements.

• Why are you so smart?

• Does this also count leftover gas? Say, at station i, we have 2 units extra gas, which comes in handy at station i+1, where we fall 1 unit of gas short. Does this come under the purview of the question, and if yes, I'm not sure where this is accounted for in the code