# Simple C++ O(N) solution with explanation

• I define `need` as how much gas we need to go to next station. It can be negative or positive.
• I define `start` as the start station of this circle and `i` as the station trying to move forward.
• `if need > 0`, that means we need gas, so we move backward trying to gain more gas.
• `if need <= 0`, that means we get enough gas, so try to move forward.
• `if i == start`, that means we have traveled a circle. we check `need` and return the result.
``````class Solution {
public:
void decrease(int size, int &curr) {
if (curr > 0)
--curr;
else
curr = size - 1;
}
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int size = gas.size();
int start = 0;
int need = 0;
for (int i = 0; i < gas.size();) {
if (need > 0) {
decrease(size, start);
need = cost[start] + need - gas[start];
} else {
need = cost[i] + need - gas[i];
++i;
}
#if 0
cout<<"i: "<<i<<endl;
cout<<"start: "<<start<<endl;
cout<<"need: "<<need<<endl;
cout<<endl;
#endif
if (i == start)
break;
}
if (need > 0)
return -1;
else
return start;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.