FIND THE STARTING POINT OF THE CYCLE | Knowing Algorithm is Okay, But Knowing The Intuition Matters

[@takeUforward]

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 :)

[@PriyanshuKumar-bx9oy]

Sorry but I didn't understood how you have written L1=nc-L2 ?

[@anuragshekhawat]

Slow pointer can never make more than two turns in loop.

[@anuragshekhawat]

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.

[@allmighty2000]

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]

Glad :)

[@scorcism.]

damm extraordinary explanation

[@abhay9994]

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!

[@vijaykumar-b6i7t]

@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.

[@abhinavbhar645]

this needs more likes so it goes up

[@shubhamjain54519]

5:30 optimized approach tortoise hare 7:50 step2 10:20 intuition/proof 14:10 code

[@LeetDaily]

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.....

[@AZ-kh9ex]

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 ...

[@amanshrivastava908]

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

[@aryanverma7800]

@@amanshrivastava908 there is something called time buddy

[@crushed_oreos]

Thanks for explaining the intuitions so clearly Striver, really makes coding up the solution a bit easier. ❤

[@kaustav07]

Finally the intuition is clear.

[@ritikatiwari3753]

you are such an amazing person you have saved so many lives god bless you!!! lots and lots of love and power to you.

[@wanderer_ankur]

This question's approach was very similar to the first question of SDE sheet. Thank you strive for helping so much :)

[@prakashjha7238]

Thanks for the math behind the algorithm! I also wish to be guiding person to many.

[@rahulgovindkumar3105]

That was an awesome intuition explanation .......... really really really thank you so much for your efforts

[@byomakeshpanda8055]

That intuition part 🤩. Thanks Striver ❤❤

[@gatishmehta2039]

This is exactly what I was looking for. Thank you so much! :)

[@ranasauravsingh]

UNDERSTOOD... !!! Thanks striver for the video... :)

[@jayachandra677]

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!

[@takeUforward]

Was the intuition clear?

[@aysams2]

@@takeUforward yes sir, it certainly was.

[@amitpaunikar3408]

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

[@takeUforward]

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 :)

[@satyamgupta6030]

thanks alot striver ur explaination's are very good and easy to understand.

[@NeerajSharma-mz4es]

Want to understand the concept in minimal time with all approaches this is the channel

[@priyanshumahato5270]

dude this explanation was the best soo far : )

[@rishabhrathore1727]

you make look these algorithms questions soo easy man i am in love with your content

[@subhamrajgarhia2524]

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; } }

[@sudiptadas2806]

You have explained the problem in a very easy way. thanks a lot

[@gowdhamt1651]

Perfect explanation about the Intuition , Thank you!!

[@tirthpatel20]

nice intuition #striver especially for the entry pointer and slow pointer point to find cycle start point.

[@AKASH-sw9bs]

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 .

[@stevewilsonraj]

thank you striver !!!

[@priyaj9908]

Your explanation is very clear and understandable. Thank you so much😊

[@shikharathaur6664]

Such a wonderful explanation of intuition. Thanks for the efforts !

[@AkhileshKumar-lv7yv]

Thank you for the explanation!

[@thelimit9719]

in interviews, apart from algos , do they ask qns like implement ds like a deque, circular linked list etc ?

[@willturner3440]

Yup

[@kaichang8186]

understood, thanks for the great explanation

[@abhinilnath1900]

BRILLIANT INTUTION

[@ragnarT3]

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 😀

[@takeUforward]

oh chair awaaz krta front back jb krta hun

[@lightninghunterCR]

Understood!! And damn that intuition reminds me of Discrete Mathematics!

[@tanushree0106]

Thank you so much raj bhaiya..may god always bless you😇

[@rohithreddy8976]

This is the only video where I understood intuition. Thank you so much, Bro

[@VaishnaviNigam]

BESTTTTT EXPLAINATION🤩🤩🤩🤩🤩🤩

[@binodbinod7537]

Thank you soo much for the video ❤️🙏

[@nagame859]

One of the best explanations of yours! 🎩📴

[@sahilgoyals]

Super Clear, Thank you so much sir 🤩

[@SATYAPRAKASH-ph1kk]

very well explained in detail and also the code is very to understand and code

[@sayantaniguha8519]

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 ?

[@arhitakundu5846]

The best explanation on youtube!

[@meshkatuddinahammed]

Bro, when about the string playlist is coming? Eagerly waiting for it. Thanks!

[@kamalnayan5331]

Thanks for the video .🌞

[@Steve_Chandan]

really i like your explanation all the time.😊😊😊

[@kewaltakhellambam7710]

such an intricate solution! Nice

[@krishanusaha5212]

Great Explanation 🔥

[@hardikagarwal3938]

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?

[@anuragjana111]

Same question

[@DTMAPunitSingh]

You can add n1C to slow pointer and you will get same result

[@adityavishalsingh8624]

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.

[@devangsingh2950]

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?

[@rohangangwar6604]

bhaiya jitna mja algo me ni aaya usse kahi jada intution se aaya...thank u so much bhaiya

[@uptonogood300]

was able to solve it with little different approach even before seeing the solution . thanks to the previous videos in the playlist !

[@sourabhchoudhary7289]

will you please share you approach/code ??

[@Hound77]

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?

[@sumekagarwal8229]

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.🤶

[@dhanashreegodase4445]

Thanks for the effort

[@prathamjain8937]

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

[@tanishkumar5827]

well explained !

[@shivamgupta336]

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 .

[@sourabhkumar6194]

That verification part explained very well

[@subhadeepsadhukhan2875]

Thank you

[@vickyarora7380]

Very helpful!

[@dreamyme543]

Great explanation , Thank you:)

[@welcometoc.s.easpirants]

You Rock Man.

[@jackisname6825]

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

[@PriyanshuKumar-bx9oy]

Can anybody elaborate how L1 becomes equal to nc-L2 in general not from equation?

[@mukuljain4087]

but why are you not considering the cycle of slow pointer

[@ritikashishodia675]

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

[@ritikashishodia675]

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....

[@AbhishekKumar-td5zu]

Tqsm bhaiya ♥️♥️

[@Yag116]

cant we add a condition to optimize TC as at 6:48 slow already collides with fast pointer ?

[@auroshisray9140]

Great explanation as always.

[@-ShangsitNath]

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?

[@crushed_oreos]

yes, so if we do n iterations, fast pointer covers 2*n steps and slow pointer covers 1*n steps

[@shashankgsharma0901]

Understood!

[@gauravtripathi9456]

Wow, such a good explanation of the intuition behind the algorithm. Thanks for the effort !

[@letsexplore7590]

Thanks Bhaiya thanks 🙏

[@bhavyagarg9763]

The explanations are very precisely explained and hence easy to understand . Thanks a lot for the amazing content. Keep up the good work.

[@sadabhalim5806]

Love you brother :)

[@bhaveshsoni6684]

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?

[@takeUforward]

Yes it is, but modifying given data is not allowed generally if it can be done without it.

[@gayathrijaini2386]

Is it nC-l2 or C-l2. Bcoz one cycle length is c right? 🤔

[@sathwikabhignan1862]

exactly, I also have the same doubt here

[@HDbIce-oj3wv]

Thanks bahiya 👍

[@be_like__prateek]

@take U forward Bhai how many iterations will fast pointer loop within the loop in the worst case ? Is the answer 2 ??

[@accepted5856]

same doubt

[@yatinarora1252]

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

[@shafeymalik5334]

can anyone answer is it possible if the entry and slow keeps revolving anf they never meet?

[@anilyadav-ky1bg]

Hi Bhayia, in outer loop while i was like

[@gnaneshwarkandukuri6733]

how fast pointer dist=2* slow pointer....?

[@astrid_6622]

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

[@sathwikabhignan1862]

yeah how de we know that

[@madanmohan5661]

Can someone tell me after detecting the loop how we can remove it from the list?

[@shivamchauhan029nitjsr4]

bhaiya agar input mein non-cyclic linkedList ajati h (in case) to while loop SEGGS dega i guess.

[@jaihari1404]

hey hey hey good explanation,but i hava an problem where can i learn this type of "maths":::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::>>>>>>>>>>>>>>>>>>>

[@practice8844]

Best teacher ever

[@gigachadkartik]

mazedaar, nice video

[@rudrasimhaa269]

Anybody know who is the Genius that first come up with this idea?

[@gourabsinha]

Why not we are making the fast pointer jumps three nodes?

[@takeUforward]

it been stated in the previous video... already said that in the video

[@gourabsinha]

@@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?

[@takeUforward]

No the chances of colliding sooner is with fast jumping twice :)

[@thelimit9719]

@@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

[@TomJerry-bp9ig]

Awsm❤

[@amritraj658]

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 🙏

[@ShubhP-t2c]

5:23

[@rahulnavgire2461]

you are great

[@judgebot7353]

unique algo

[@shyamjeegupta6173]

would not the TC of first approach be O(NlogN), logN for searching the given address is present in hash table or not ?? Thanks

[@crushed_oreos]

in c++ time complexity for searching an element in unordered set is O(1)

[@binodbinod7537]

Hi bhaiyaa ❤️