# Clean simple solution well-explained and accepted as best submission in C

• Since we are required to find the only one available solution then we can just search for the most possible one first and then check its validity - bang, problem solved! Here is the basic idea:

• there is a thing you need to remember that the circle is from i to i+1, so when we back check the most possible start index, we should start from the last gas station;
• we are clear that once we pass one gas station we will get another refill gas[i]-cost[i] (this can be negative or positive);
• in each gas station we can might encounter the max amount of remained gas to the last one and then we can update the maximal remained gas and record the index;
• after traversing from the last to the first, we now get the maximal remained gas and the corresponding index and then we check it whether it's invalid - less than zero which means the circle can never be finished.

``````//AC - 0ms;
int canCompleteCircuit(int* gas, int gSize, int* cost, int cSize)
{
int index=-1, total=0, max=-1;
for(int i = size-1; i > -1; i--)
{
total += gas[i]-cost[i];
if(total > max)  index=i, max=total;
}
return total < 0? -1 : index;
}``````

• Can you explain why it should start from the last ?

I feel your explanation is not well explained for updating the index when a larger value is encountered.

Thanks.

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