# My solution using idea of two pointers

• My idea is simple and can be broken down into two parts:

1. If accumulated balance is positive, we simply advance to the next city
2. If not, a backward search of start point and update balance

The rest of code is just corner case handling.

``````int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
if (gas.size() == 1)    return gas[0] >= cost[0] ? 0 : -1;

int start = 0, ptr = start, tar = start + 1, balance = 0;

while (start != tar) {
int now = balance + (gas[ptr] - cost[ptr]);

if (now >= 0) {
balance = now;
ptr = POS(ptr+1, gas.size());
tar = POS(tar + 1, gas.size());
} else {
//Backward
start = POS(start - 1, gas.size());
balance += gas[start] - cost[start];
now += gas[start] - cost[start];

if (start == tar && now < 0)
return -1;
}
}

return balance + (gas[ptr] - cost[ptr]) >= 0 ? start : -1;
}
``````

Note:

POS() is a macro that simply return correct position in a circular array

define POS(n, l) ((n) < 0 ? ((l) - 1) : ((n) % (l)))

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