C++ Solution: github.com/striver79/SDESheet/blob/main/detectStartOfLoop_C%2B%2B Java Solution: github.com/striver79/SDESheet/blob/main/detectStartofLoop_Java Do check me at Instagram(Striver_79) to know all about the success stories, and attend the live interactions that I keep doing :)
At any point if slow pointer enters loop, after travelling half distance of loop, slow pointer bound to meet fast. I am assuming slow pointer takes 1 step and fast takes two steps.
intuition that When I first heard that we can’t use a hash table , The first thing came at my mind , it’s like A is a person he is going into a forest , roaming around , and then he observed that he is lost by remembering that he just visited that place , but we are told not to use hash table , So it’s just like A is a person with memory loss , so let’s assume B is his brother he also come the same way to find his brother but he will be also lost too , And their speed must differ so that they find out each other (collide) But I thought my idea is wrong as it’s not possible to calculate their starting position by collision theory , Now I am seeing , that don’t be lazy imaging , just grab pen and paper and do some work to find out relations , @Raj bhaia thanks 🙏
@takeUforward hii, i think there is a slight change in the intution equation. it should be like 2(l1+l2+k(c) )=l1+l2+n(c). because pointers are not bound to collide in the first iteration it self that you mentioned in the video but was missing in the equation, writing the equation in this way seems better to me. overall its good, and thanks for the playlist, it's wonderful.
Dear Striver, I wanted to send you a heartfelt thank you for your tireless dedication to teaching DSA for free. Your selflessness and passion for helping students with their job interview preparation have made a significant impact on my life and countless others. I am incredibly grateful for the knowledge and confidence you have imparted to us. Thank you for everything you do!
instead of nC we may write 1 cycle because as fast pointer completes two cycles slow pointer will complete atleast one and that we are adding in L2.....
Yeah Striver himself claimed in his latest course related Cp course post he learned everything googling and finding online tutorials. These course is for those people who can't go without spoonfeeding and cannot self learn from themselves
Hi ... Good explanation of all topics Some linked list question is remaining Clone a list with next and random pointer Detect a cycle and remove loop from list Waiting for this topic video
Everything will come :), with the help of this problem you can remove the loop also, just keep track of the previous pointer to slow when slow meets the entry pointer, so you can easily point the previous pointer to NULL, and you were successful in removing the loop :)
10:03 Even if we write *entry=head* separately, it wont affect space complexity. Cuz, we are using 'entry' pointer to traverse a part of the list . We are not inserting nodes into it . Right ?
I solved this today in the morning, I luckily assumed that the head pointer will always meet the slow pointer at some point. When I tried it for a couple of examples, I understood that my assumption was true and my code got accepted. Thank you for your thorough explanation bhaiya!
I have a doubt if we take a fast pointer travelling twice the distance than slow pointer, they are bound to meet and then we can find the starting node of the linked list by travelling from the meeting point. What if they move at random speeds fast = 3*slow, then also they are bound to meet(Using hash table probing logic) but then how can we find the start of the cycle then?
L2 is the dist covered by slow pointer, which may include some cycles and the dist from entry point to point of intersection. So how the L1 = nC-L2 be certainly equal to the remaining dist of the cycle?
12:55 Doesn't matter if slow have covered Cycles or not .. let's assume it have some cycles (x turns) and for sure if slow have cycle so fast will cover cycle(y turns) more than the slow one... So to make things convenient you can make x to zero and corresponding update y to (y-x) .. hope it now make sense.
what a clean explanation .. i also watched the video from some of the other youtube tutorials but they represented the same thing in a much more complex way... Thanks brother for making the algorithm so simpler to understand .
Since time complexity is O(n) means we are sure that slow pointer and fast will meet before the slow traverses all the elements .I mean how are we sure that slow will not loop more than once in cycle before meeting fast . Can someone please explain
i have a question striver if suppose slow and fast pointer will collide at node(8) then i guess slow and entry pointer will never point to the same node according to the operations applied on slow and entry pointer?? please answer this question
There is some kind of flute like sound coming... 2:45-2:50 here it is clearly noticeable. Great work bhai... Just thought of letting u knw about the noise 😀
Which hash table to use in the naive approach? set or a map? and how to store it...........set? class Solution { public: ListNode *detectCycle(ListNode *head) { set s; ListNode * tmp = head; while(tmp!=NULL){ if(s.find(tmp)!=s.end()){ return tmp; } s.insert(tmp); tmp=tmp->next; } return NULL; } }; please correct this.🤶
Bhaiya hashing mind m ai O(1) nahi Hua usme ek problem ai us cycle s jo extra node h uski vjh s . Agr slow or fast us cycle k start pr khade ho to same honge kuch us loop m travel krne k bd
I used one approach to solve the same problem with exactly o(n) complexity. In this approach, I changed the value of every node with my name. if I find my name again, then it is the Cycle starting point. Is it the right approach?
how do we know that nc-L2 is the distance needed to be travelled by slow pointer ? i am assuming the fast pointer only takes on turn more to reach upto slow pointer
Yes it is taking twice the number of iterations so it will take 2 iterations kind of and regarding it may happen in wrost case they won't find any cyclr
@@takeUforward but it's for only fast pointer jumping two times that doesn't clear my doubt. Let's say a vehicle A is having v speed and other vehicle B which is having 3v speed and distance between them is D where A is in front of B. Then also B will catch A after some time for sure as speed of B > A. Then why aren't we considering that one. It will be faster know?
@@gourabsinha correct me if im wrong . i think its not guarenteed with 3 jumps they collide. for eg: t=0, posA=3, posB=0, speedA=1, speedB=3 t=1, posA=4, posB=3 t=2, posA=5,posB=6 now impossible to collide. but u take any example of ur choice and use fast as 2jumps ahead, they r bound to collide
hey hey hey good explanation,but i hava an problem where can i learn this type of "maths":::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::>>>>>>>>>>>>>>>>>>>
I m in 11 th tried c++ in lockdown and i like it and gonna make my courier in cs but i cant give jee or crack big iit but really wanna succesful in the field plz help
Let s be the speed of slow pointer and f be the speed of speed pointer and we know that f = 2 * s Let d1 be the distance covered by slow one and d2 be the distance covered by speed pointer and we know that (distance = speed / time) so, d1/d2=s/f d1/d2=s/2*s d1/d2=2 so, d2 = 2 * d1
Mostly ! The STL you use can also be implemented using LinkedList. Since we use so much of STL, we don't care about the implementation. Hence these things are asked at Interviews!
C++ Solution: github.com/striver79/SDESheet/blob/main/detectStartOfLoop_C%2B%2B
Java Solution: github.com/striver79/SDESheet/blob/main/detectStartofLoop_Java
Do check me at Instagram(Striver_79) to know all about the success stories, and attend the live interactions that I keep doing :)
Sorry but I didn't understood how you have written L1=nc-L2 ?
Slow pointer can never make more than two turns in loop.
At any point if slow pointer enters loop, after travelling half distance of loop, slow pointer bound to meet fast. I am assuming slow pointer takes 1 step and fast takes two steps.
5:30 optimized approach tortoise hare
7:50 step2
10:20 intuition/proof
14:10 code
intuition that When I first heard that we can’t use a hash table ,
The first thing came at my mind , it’s like A is a person he is going into a forest , roaming around , and then he observed that he is lost by remembering that he just visited that place , but we are told not to use hash table ,
So it’s just like A is a person with memory loss , so let’s assume B is his brother he also come the same way to find his brother but he will be also lost too ,
And their speed must differ so that they find out each other (collide)
But I thought my idea is wrong as it’s not possible to calculate their starting position by collision theory ,
Now I am seeing , that don’t be lazy imaging , just grab pen and paper and do some work to find out relations ,
@Raj bhaia thanks 🙏
Glad :)
damm extraordinary explanation
@takeUforward hii, i think there is a slight change in the intution equation. it should be like 2(l1+l2+k(c) )=l1+l2+n(c). because pointers are not bound to collide in the first iteration it self that you mentioned in the video but was missing in the equation, writing the equation in this way seems better to me. overall its good, and thanks for the playlist, it's wonderful.
this needs more likes
so it goes up
Dear Striver,
I wanted to send you a heartfelt thank you for your tireless dedication to teaching DSA for free. Your selflessness and passion for helping students with their job interview preparation have made a significant impact on my life and countless others. I am incredibly grateful for the knowledge and confidence you have imparted to us. Thank you for everything you do!
instead of nC we may write 1 cycle because as fast pointer completes two cycles slow pointer will complete atleast one and that we are adding in L2.....
Irony is none of those 7* or red coders would have ever joined such a subscription plan ( as unacademy's ) to reach where they are ...
Yeah Striver himself claimed in his latest course related Cp course post he learned everything googling and finding online tutorials. These course is for those people who can't go without spoonfeeding and cannot self learn from themselves
@@amanshrivastava908 there is something called time buddy
Finally the intuition is clear.
THIS IS MORE OPTIMAL APPROACH
public class Solution {
public ListNode detectCycle(ListNode head) {
Map map = new HashMap();
ListNode slow = head;
ListNode fast = head;
while(fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if(slow == fast) {
ListNode p1 = head;
ListNode p2 = slow;
while(p1 != p2) {
p1 = p1.next;
p2 = p2.next;
}
return p1;
}
}
return null;
}
}
Thanks for explaining the intuitions so clearly Striver, really makes coding up the solution a bit easier. ❤
you are such an amazing person you have saved so many lives god bless you!!! lots and lots of love and power to you.
This question's approach was very similar to the first question of SDE sheet. Thank you strive for helping so much :)
That was an awesome intuition explanation .......... really really really thank you so much for your efforts
Thanks for the math behind the algorithm!
I also wish to be guiding person to many.
in interviews, apart from algos , do they ask qns like implement ds like a deque, circular linked list etc ?
Yup
That intuition part 🤩.
Thanks Striver ❤❤
This is exactly what I was looking for. Thank you so much! :)
UNDERSTOOD... !!!
Thanks striver for the video... :)
Hi ... Good explanation of all topics
Some linked list question is remaining
Clone a list with next and random pointer
Detect a cycle and remove loop from list
Waiting for this topic video
Everything will come :), with the help of this problem you can remove the loop also, just keep track of the previous pointer to slow when slow meets the entry pointer, so you can easily point the previous pointer to NULL, and you were successful in removing the loop :)
thanks alot striver ur explaination's are very good and easy to understand.
nice intuition #striver especially for the entry pointer and slow pointer point to find cycle start point.
dude this explanation was the best soo far : )
10:03
Even if we write *entry=head* separately, it wont affect space complexity.
Cuz, we are using 'entry' pointer to traverse a part of the list .
We are not inserting nodes into it .
Right ?
Perfect explanation about the Intuition , Thank you!!
I solved this today in the morning, I luckily assumed that the head pointer will always meet the slow pointer at some point. When I tried it for a couple of examples, I understood that my assumption was true and my code got accepted. Thank you for your thorough explanation bhaiya!
Was the intuition clear?
@@takeUforward yes sir, it certainly was.
Want to understand the concept in minimal time with all approaches this is the channel
You have explained the problem in a very easy way. thanks a lot
Such a wonderful explanation of intuition. Thanks for the efforts !
I have a doubt if we take a fast pointer travelling twice the distance than slow pointer, they are bound to meet and then we can find the starting node of the linked list by travelling from the meeting point. What if they move at random speeds fast = 3*slow, then also they are bound to meet(Using hash table probing logic) but then how can we find the start of the cycle then?
L2 is the dist covered by slow pointer, which may include some cycles and the dist from entry point to point of intersection. So how the L1 = nC-L2 be certainly equal to the remaining dist of the cycle?
Same question
You can add n1C to slow pointer and you will get same result
12:55
Doesn't matter if slow have covered Cycles or not .. let's assume it have some cycles (x turns) and for sure if slow have cycle so fast will cover cycle(y turns) more than the slow one... So to make things convenient you can make x to zero and corresponding update y to (y-x) .. hope it now make sense.
you make look these algorithms questions soo easy man
i am in love with your content
Understood!! And damn that intuition reminds me of Discrete Mathematics!
Thank you soo much for the video ❤️🙏
BRILLIANT INTUTION
Your explanation is very clear and understandable. Thank you so much😊
thank you striver !!!
Thank you for the explanation!
understood, thanks for the great explanation
This is the only video where I understood intuition. Thank you so much, Bro
what a clean explanation .. i also watched the video from some of the other youtube tutorials but they represented the same thing in a much more complex way...
Thanks brother for making the algorithm so simpler to understand .
very well explained in detail and also the code is very to understand and code
Since time complexity is O(n) means we are sure that slow pointer and fast will meet before the slow traverses all the elements .I mean how are we sure that slow will not loop more than once in cycle before meeting fast . Can someone please explain
BESTTTTT EXPLAINATION🤩🤩🤩🤩🤩🤩
bhaiya jitna mja algo me ni aaya usse kahi jada intution se aaya...thank u so much bhaiya
Super Clear, Thank you so much sir 🤩
Thank you so much raj bhaiya..may god always bless you😇
why are we checking for fast->next && fast->next->next is there any edge case which we will miss if we use fast->next && fast?
The best explanation on youtube!
i have a question striver if suppose slow and fast pointer will collide at node(8) then i guess slow and entry pointer will never point to the same node according to the operations applied on slow and entry pointer?? please answer this question
Bro, when about the string playlist is coming? Eagerly waiting for it. Thanks!
One of the best explanations of yours! 🎩📴
There is some kind of flute like sound coming... 2:45-2:50 here it is clearly noticeable. Great work bhai... Just thought of letting u knw about the noise 😀
oh chair awaaz krta front back jb krta hun
cant we add a condition to optimize TC as at 6:48 slow already collides with fast pointer ?
Which hash table to use in the naive approach? set or a map?
and how to store it...........set?
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
set s;
ListNode * tmp = head;
while(tmp!=NULL){
if(s.find(tmp)!=s.end()){
return tmp;
}
s.insert(tmp);
tmp=tmp->next;
}
return NULL;
}
};
please correct this.🤶
was able to solve it with little different approach even before seeing the solution . thanks to the previous videos in the playlist !
will you please share you approach/code ??
Bhaiya hashing mind m ai O(1) nahi Hua usme ek problem ai us cycle s jo extra node h uski vjh s . Agr slow or fast us cycle k start pr khade ho to same honge kuch us loop m travel krne k bd
Thank u bhaiya bs ek point nahi such payi last vala ki Jo gap arra h start or phuchne m cycle k vo entry s pura ho skta h 🤩🤩🤩 thanks a lot bhaiya....
such an intricate solution! Nice
That verification part explained very well
I think you have not considered one condition if fast and slow pointer meets at starting point. In this case entry and slow are giving wrong answer .
can anyone answer is it possible if the entry and slow keeps revolving anf they never meet?
I used one approach to solve the same problem with exactly o(n) complexity. In this approach, I changed the value of every node with my name. if I find my name again, then it is the Cycle starting point. Is it the right approach?
Yes it is, but modifying given data is not allowed generally if it can be done without it.
Thanks for the video .🌞
how do we know that nc-L2 is the distance needed to be travelled by slow pointer ? i am assuming the fast pointer only takes on turn more to reach upto slow pointer
yeah how de we know that
really i like your explanation all the time.😊😊😊
why distance travelled by fast pointer is twice the distance travelled by slow pointer?? Is it bcoz, fast pointer is taking 2 steps at a time?
yes, so if we do n iterations, fast pointer covers 2*n steps and slow pointer covers 1*n steps
bhaiya agar input mein non-cyclic linkedList ajati h (in case) to while loop SEGGS dega i guess.
5:23
Great explanation , Thank you:)
@take U forward Bhai how many iterations will fast pointer loop within the loop in the worst case ?
Is the answer 2 ??
same doubt
Yes it is taking twice the number of iterations so it will take 2 iterations kind of and regarding it may happen in wrost case they won't find any cyclr
Can someone tell me after detecting the loop how we can remove it from the list?
Great Explanation 🔥
Wow, such a good explanation of the intuition behind the algorithm. Thanks for the effort !
Is it nC-l2 or C-l2. Bcoz one cycle length is c right? 🤔
exactly, I also have the same doubt here
but why are you not considering the cycle of slow pointer
Bhaiya mai core branch se hu 1st year...kya mai IT Related company me ja sakta hu as a SDE, mai start kar diya programming sikhna ...... plz reply 🙏
how fast pointer dist=2* slow pointer....?
Can anybody elaborate how L1 becomes equal to nc-L2 in general not from equation?
Hi Bhayia, in outer loop while i was like
would not the TC of first approach be O(NlogN), logN for searching the given address is present in hash table or not ??
Thanks
in c++ time complexity for searching an element in unordered set is O(1)
Anybody know who is the Genius that first come up with this idea?
ListNode *detectCycle(ListNode *head) {
ListNode*fast = head;
ListNode*slow = head;
bool cycle = false;
while(fast != NULL && fast->next != NULL){
slow = slow->next;
fast = fast->next->next;
if(slow == fast){
cycle = true;
break;
}
}
if(!cycle)
return NULL;
ListNode*temp = head;
while(temp != slow){
slow = slow->next;
temp = temp->next;
}
return slow;
}
};
You Rock Man.
Thanks for the effort
Why not we are making the fast pointer jumps three nodes?
it been stated in the previous video... already said that in the video
@@takeUforward but it's for only fast pointer jumping two times that doesn't clear my doubt. Let's say a vehicle A is having v speed and other vehicle B which is having 3v speed and distance between them is D where A is in front of B. Then also B will catch A after some time for sure as speed of B > A. Then why aren't we considering that one. It will be faster know?
No the chances of colliding sooner is with fast jumping twice :)
@@gourabsinha correct me if im wrong . i think its not guarenteed with 3 jumps they collide. for eg: t=0, posA=3, posB=0, speedA=1, speedB=3
t=1, posA=4, posB=3
t=2, posA=5,posB=6
now impossible to collide.
but u take any example of ur choice and use fast as 2jumps ahead, they r bound to collide
Understood!
The explanations are very precisely explained and hence easy to understand . Thanks a lot for the amazing content. Keep up the good work.
Great explanation as always.
well explained !
hey hey hey good explanation,but i hava an problem where can i learn this type of "maths":::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::>>>>>>>>>>>>>>>>>>>
Best teacher ever
Very helpful!
mazedaar, nice video
Tqsm bhaiya ♥️♥️
ListNode *detectCycle(ListNode *head) {
if( head == NULL || head->next ==NULL )
return NULL;
ListNode* slow = head;
ListNode* fast = head;
while(fast->next && fast->next->next){
fast = fast->next->next;
slow = slow->next;
if(fast == slow){
slow=head;
//REUSING SLOW POINTER;
while(fast !=slow){
slow = slow->next;
fast = fast->next;
}
return fast;
}
}
return NULL;
}
Thank you
I m in 11 th tried c++ in lockdown and i like it and gonna make my courier in cs but i cant give jee or crack big iit but really wanna succesful in the field plz help
Thank you so much bhaiya for such amazing explanations
Can you please explain this
Why 2(L1 + L2) = (L1 + L2 + nC)
Let s be the speed of slow pointer and f be the speed of speed pointer
and we know that f = 2 * s
Let d1 be the distance covered by slow one and d2 be the distance covered by speed pointer
and we know that (distance = speed / time)
so, d1/d2=s/f
d1/d2=s/2*s
d1/d2=2
so, d2 = 2 * d1
@@dineshchintu9779 ur ryt about everything just change the distance formula since, distance=speed*time :-)
Love you brother :)
I have never encountered any linked list q in any cp platform. Is linked list interview specific?
Mostly ! The STL you use can also be implemented using LinkedList. Since we use so much of STL, we don't care about the implementation. Hence these things are asked at Interviews!
Hi bhaiyaa ❤️