Circular tour problem

This problem is one of the most important problem from the topic of stack and queue for interview preparation. The problem is find the minimum index of the city from where we can make a circular tour and cover all the cities (if possible). The time complexity of efficient approach is only O(N). CODE LINK is given below. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)

[arjunkashyap]

This was such a simple logic and yet it never occurred to me. Love your way explaining.

[ShreyaSingh-vrqi]

Best explaination seen so far for this problem!! Thanks @TechDose

[jajateenandineesahoo]

Loved your explanation. Very easy and simple to understand but it would have been great if you explained the code also by doing dry run as the code you have provided is the same as in GFG.

[Chandutravelvlogs]

faculties also may not be explain like this, thank you sir thank you so much, I love to learn by watching your youTube videos

[utkarshbahukhandi]

rather than traversing twice we can actually use a negative balance variable which stores all negative balances obtained so far and only front variable, so when you reach at the end just check for balance+ negative balance value if >=0 then front is the required answer else -1

[awesome_latest_virals]

Sir, Your vedios are very very helpful, aap un logo me se hain jinka ehsaan main kabhi nahi chuka paaunga !! thank u so much for all your vedios and explainations!!!

[arunsp]

If you have any doubt, please watch the video again😂

[ultiumlabs]

awesome, finally I can understand the algorithm, thank you

[emilyhuang]

Why is it that the code does not implement the explanation in the video where you update the start to the current end, but in the code the start is moved up one by one?

[sabarishraj]

Hello pradaph, the first scenario is not able to make circle. Could you please ensure.

[karmukil]

Bro your videos are very useful..kudos to you!

[EngWorld-nrww]

quite simple and effective explanation..

[abhilashpaul]

are you the same person who also teaches in apna college ? your sound seems familiar and btw its my first time visiting your channel.

[abhishekgautam]

How to handle the case when balance is negative for each element of the array?
Do we have to create a map for counting the no. of visits for each element of the array?

[hymnish_you]

I think what you told at 8:40 is wrong, We can't merge it that way as to what if sum till arr.length = 1, but at index 0 the difference between gas and cost was -4! Can you clarify? Anyways thanks fr ur vids.

[sahiljitsandhu]

in the first example... if we start from index 3 .. then also we can't complete the circular tour... u said wrongly that we can.

[pawankumarpandit]

sir aapka aawaz se dr lgta hai bs baaki explanation to bawal hai sir

[VikashKumar-ugjx]

thanks sir, your way of explaining concept is mindblowing,
code for whom not able to write:
int tour(petrolPump p[], int n)
{
int bal=0, f=0, r=n-1, v, s=0;
if(n==1) return 0;
bool t=1;//flag
for(int i=0;i<2*n;i++)
{

if(f==r&&t==1)
return s;
if(v>=0)
{
f=(f+1)%n;
t=1;
bal=v;
}
else
{ s=(i+1)%n;
bal=0;f=r=(i+1)%n;
t=0;
}
}
return -1;

}

[mailtobasit]

class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {

int remainingPetrol = 0;

int shortOf = 0;

int front = 0;
int rear = 0;

while (rear < gas.length) {

if (remainingPetrol + gas[rear] >= cost[rear]) {

remainingPetrol += gas[rear] - cost[rear];

rear++;
continue;

}

shortOf += (remainingPetrol + gas[rear]) - cost[rear];

front = rear + 1;
rear = rear + 1;

// reset
remainingPetrol = 0;

}


return (shortOf + remainingPetrol >= 0) ? front : -1;


}
}

[LightYagami-ibfb]

All this traversing twice and other jargons can be avoided with a simple observation that if the difference of (petrol - distance) in each step sums upto a negative value we can never have any starting index and thus we can return -1, or else use this two pointer technique to find out the leftmost starting position.