O(n) time complexity and O(n) space solution with approach explained


#1

Hi there
Before stating I have put approx 1 hours to design this solution, so please read the complete article. The extra space of n size used in this approach can be avoided but I have kept it to simplify the explanation.
Firstly, we will make an array of extra fuel available at each station, i.e. gas available at that station minus gas required to move to next station and also we will do sum of these i.e total extra fuel, if total extra fuel<0 ,it means that it tis impossible to complete cycle irrespective of starting position so return -1.
After that we will start from index 0 and traverse the extra fuel array which we made earlier and update a variable total extra, to make sure that we are not stuck at any station while completing cycle, we need to make sure that this total extra variable should always be positive
If it becomes negative, we will check from next position.
Now if initially you got total_extratime>=0, it guarantees that solution is possible.

int Solution::canCompleteCircuit(const vector &A, const vector &B)
{
int i,j,total_extra=0,n=A.size(),x;
vector extra_gas;
for(i=0;i<n;i++)
{
//x is extra gas at each station
x=A[i]-B[i];
extra_gas.push_back(x);
total_extra+=x;
}
if(total_extra<0)
return -1;
i=0;
while(i<n)
{
total_extra=0;
j=i;
for(j=i;j<i+n;j++)
{
int k=j%n;
total_extra+=extra_gas[k];
if(total_extra<0)
{
i=j+1;
break;
}
}
if(j==(i+n))
return i;
}
}

Please comment if you need further explanation
Do enlighten me if you have better solution


#2

Time complexity is not O(n)