# My AC is O(1) space O(n) running time solution. Does anybody have posted this solution?

• I have got one solution to this problem. I am not sure whether somebody has already posted this solution.

``````class Solution {
public:
int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {

int start = gas.size()-1;
int end = 0;
int sum = gas[start] - cost[start];
while (start > end) {
if (sum >= 0) {
sum += gas[end] - cost[end];
++end;
}
else {
--start;
sum += gas[start] - cost[start];
}
}
return sum >= 0 ? start : -1;
}
};``````

• pretty good solution! and it's easy to understand.

• Can someone explain why the running time in worst case is not O(n^2)? Thanks.

• During every iteration of the while loop, either end increases by 1 or start decreases by 1, so the while loop has exactly N-1 iterations.

• How can this method list all the possible start index i ?

• This post is deleted!

• this one is nicer than the most voted thread.

• Can you please explain the solution??

• Take the begin (0) as end and end( gas.size()-1 ) as start is really brilliant !
I have the similar idea but I must deal with edge cases when start gets at 0 or end gets at end(gas.size()-1).
You avoid these edge cases with this trick!

## I am not the owner of this solution, here is some explanation according to the code.

The main idea is that every time we go to the next station as far as possible (remained gas is bigger or equal to 0) until we can not (remained gas is less than 0).
Then we must extend our start station to the "last station" ( the station before start station) to find a possible solution.
Repeat these two steps until we have checked all stations(start == end).

We can travel around the circuit only if the remained gas is bigger or equal to 0!

• @yanchao_hust Thanks for the explanation. But what's the point of `end++` while `sum >= 0` ?

• @mugua-stolaf It means when your remaining gas is greater than 0 you can try go further.

• My understanding:

The basic idea is every time we start from a station, we go as far as possible by increasing `end` until remaining gas is less than 0. If 'end' finally hits `start` we know we can travel around from 'start'. If we haven't traveled around, we know we cannot start from this station. Then we check the station before our start station if we can start from this station. Repeat until we have checked all stations.

Note there is a little trick that every time we try to find the next start station, we always to back to extend the distance from start to end so that we can check all stations on the circuit. Otherwise, if we move start forward to decrease the distance from start to end, we are likely to end up with only checking part of the circuit. Another trick is we start from the end of the array so as to avoid some corner cases.

• @yanchao_hust Are you from Wuhan?

• @hzhu007 what is wuhan ,,,haha