# 11ms - c++ solution. visiting each station once.

• ``````class Solution
{
public:
int canCompleteCircuit(vector<int> &gas, vector<int> &cost)
{
// Start from an arbitrarily chosen index, let's say 0.
// Accumulate the remaining gas (gas - cost).
//
// If there is enough gas to advance to the next station
// then advance to the next station (i++). Continue to do this
// expanding the range of traveled stations until we have
// circled back to the starting point(found a solution)
// or we have ran out of gas.
//
// If we ran out of gas it means that we should have entered the
// range with more gas, so we expand the current range to the left
// in hope to accumulate enough gas.
//
// And so on, expand to the right if we have gas, expand to the
// left if we don't have gas.
//
// Once we completed a circle we have the left side of the range (j)
// as the starting station index.
//

if (gas.size() == 0 || cost.size() == 0 || gas.size() != cost.size())
{
return -1;
}

int i = 0; // Right side of the range.
int j = gas.size(); // Left side of the range
int crt = 0; // Current index to be added to the range.
// It might be confusing that the right side of the range starts
// at 0 and the left side starts at gas.size().
// The range of stations is given by the indexes:
// j, j+1, j+2, ... , gas.size() - 1, 0, 1, 2, ..., i.

int gasSum = 0; // Remaining gas in the tank

while (i != j)
{
gasSum += gas[crt] - cost[crt];

if (gasSum >= 0)
{
// Move right
i = i + 1;
crt = i;
}
else
{
// Move left
j = j - 1;
crt = j;
}
}

if (gasSum >= 0)
{
j = j % gas.size();
return j;
}
else
{
return -1;
}
}
};``````

• Thank a lot for your code, it's very easy to understand. :)

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