# My one pass solution.

• ``````class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int size=gas.size();
int sum=0;
int res=0;
int total=0;
for(int i=0; i<size; ++i){
sum+=gas[i]-cost[i];
if(sum<0){
total+=sum;
sum=0;
res=i+1;
}
}
total+=sum;
}};
``````

The idea is simple.

1. Whenever the sum is negative, reset it and let the car start from next point.
2. In the mean time, add up all of the left gas to total. If it's negative finally, return -1 since it's impossible to finish.
3. If it's non-negative, return the last point saved in res;

• Very nice solution above, here's a re-phrased version (in Java):

• eliminating the need to `total+=sum` twice
• self-documenting code with extra (sometimes redundant) inline comments

``````private static final int EMPTY = 0;
public int canCompleteCircuit(int[] gas, int[] cost) {
assert gas != null && cost != null && gas.length == cost.length;
int start = 0;
int tank = EMPTY; // cumulated from station at start
int total = EMPTY; // extra fuel left at the end of a full circle
for (int station = 0, count = gas.length; station < count; ++station) {
int fuel = gas[station] - cost[station]; // re-fuel and drive to the next station
tank += fuel;
total += fuel;
if (tank < EMPTY) { // Ran out of gas on this circle starting from start, so
tank = EMPTY; // we're starting again
start = station + 1; // from next station.
// We already left this station when run out of gas.
// Starting anywhere (>= 0) up to this station would be futile,
// because we'll run out of gas somewhere before this station.
}
}
-1 // cannot complete the full circle, because we would run out of gas somewhere
:
start // something is left in the tank so the last starting point is valid
;
}``````

• if start = count, then your solution is incorrect.
should be return total < 0 ? -1 : (start % count);

• @dr At the time of writing I tried and it was an accepted solution.

Here's a take at reasoning: `count`th station is logically equivalent to the `0`th station as you suggested with the modulus. Notice that `start` can only take the value of `count` if you run out of gas at the last station (`count - 1`), which means you couldn't complete the full circle from `0`th station, hence you couldn't complete it starting from the `count`th station either, because they're "the same".

Do you have an input for which it returns `count`?

• Thanks. I figured out that too.

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