# C++ solution with explanation.

• ``````class Solution {
public:
//(1) Lets assume Gas[i,j] means the sum of gas from index i to index j. Same as Cost[i,j].
// (2) If Gas[0,n] >= Cost[0,n], then
//    Gas[0,k-1] + Gas[K,n] >= Cost[0,k-1] + Cost[K,n], whichs means that we can divide the array into two parts:
// [0,k-1] and [k,n]. And Gas[0,k-1]<Cost[0,k-1].
//(3) Originally, k=0(means the right array is [0,n]).
//Iterate the array, once we meet i whose Gas[k,i]<Cost[k,i],
//then  starting index will never be within [k,i]
//since its total gas < total cost. Set k=i+1.
//(4) For index within [k,n], since Gas[k,index] >= Cost[k,index], otherwise, k will be updated with index.
//So k is the starting index.
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
const int N(gas.size());
int gas_sum(0),cost_sum(0),k(0),tank_oil(0);
for(int i=0;i<N;++i){
gas_sum += gas[i];
cost_sum += cost[i];
tank_oil += gas[i] - cost[i];
if(tank_oil<0){
k = i + 1;
tank_oil = 0;
}
}
return gas_sum >= cost_sum ? k : -1;
}
};
``````

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