Duplicate number in an immutable array | Floyd cycle detection algo | Leetcode

[@Official-tk3nc]

If are watching this in lockdown believe me you are one of the rare specie on the earth who are willing to achieve something in life. Many students are wasting their time watching web-series, movies, playing pubg, all the best for your future. nitjstudenthere :))

[@techdose4u]

Nice :)

[@babbarutkarsh7770]

we aren't rare there is a lot of competition

[@AMITSHARMA-oh1nq]

@@babbarutkarsh7770 maybe field in which u are competing is the field which attracts most rarest minds

[@mopsyched]

Watching movies isnt the end of the world nor is coding

[@amar7561]

bro just gave sde-II amazon test , competitiion is very high and believe me i learnt throughout this lockdown but things did not worked for me... this data structure and system design is never enough! also they will rarely ask these types of questions again ...but yes this will improve our coding skills

[@Kacper-qp8kg]

This explanation is brilliant, actually going into the details of why this works instead of some "fast food" problem solving the *cough* most popular leetcode youtuber serves us.

[@techdose4u]

Thanks for your appreciation :)

[@RahulYadav-nl1ek]

i came here to understand the floyd's method however i am very impressed with they way you solved it assuming mutable Thanks mate!! Subscribed

[@techdose4u]

Welcome

[@shashwatbansal7776]

After seeing the solution for mutable array only one sentence came to mind "You are a genius"

[@AbhijeetMuneshwar]

Very easy to understand the concept after watching this video.

[@saikatdutta1163]

As per your explanation of the problem. Solution is pretty easy, sum of all the elements - (n * (n + 1)) / 2

[@techdose4u]

:)

[@saikatdutta1163]

@@techdose4u Am I right? or what?

[@chhatrapathisivajilakkimse1371]

@@saikatdutta1163 no not right , here you can have multiple repetitions of one element.. For test cases like 1 2 2 3 4 2

[@fabio336ful]

Easy explanation, made me understand clearly!

[@mythilikarra1902]

"So this solution is not at all intuitive" - I cackled

[@manthankhorwal1477]

I think you just complicated a point here.at 8.38 you are saying we are at index and make a node of value but when you reach 4 which has value 1 you should make node.for 1 but you jump to index 1.. ... Suppose if a number is repeating twice then there will be 2 index point to the same element So cycle entrance is always duplicate element , and harr and tortoise will work in this way only In your example 3,4,1,4,2 3->4->2->1->write here 1 will point to 4 so just point it to previous 4 in the list...

[@techdose4u]

The node pointing to intersection node will always be the repeating element. I told this in the video itself.

[@manthankhorwal1477]

@@techdose4u But your code itself return intersecting point or entrance of cycle ...There is no logic of node pointing to the intersection... You just made repeating node twice... But yours is also good.. i am a fan of your work

[@kamalsmusic]

How do you know that the collision point (where the fast and slow pointer meet) is the same distance from the duplicate element as the beggining?

[@bot7845]

thanks for the explanation everything is made crystal clear

[@vibekdutta6539]

The pigeonhole principle can also be used. Your approach is much more intuitive btw. Thanks

[@techdose4u]

The question itself is based on pigeonhole principle. The Floyd cycle algo is running on pigeonhole principle.

[@vibekdutta6539]

Yeah I didn't know that, thanks

[@techdose4u]

Welcome

[@prashantsandilya6197]

Wow sb upar se gaya...itni English 🙏

[@techdose4u]

😅

[@drashtikoladiya8313]

Your content is gold✨

[@techdose4u]

Thanks :)

[@bhavanikasiviswanathan3707]

Best video in youtube for this problem really loved it. Thank you for the video

[@techdose4u]

Welcome :)

[@bhavanikasiviswanathan3707]

Is there any video which explains floyd detection algorithm only?

[@techdose4u]

@@bhavanikasiviswanathan3707 Yea. Floyd cycle finding algorithm

[@bhavanikasiviswanathan3707]

@@techdose4u can you share me the link?

[@elizabethr5161]

Honestly, this is one of the best video explanations for this problem. After watching multiple videos for this problem, only after the TECH DOSE explanation was I able to understand it. Thanks a ton.

[@techdose4u]

Welcome :)

[@sureshgarine]

wow. awesome explanation. Thank you so much. keep doing the great work!

[@techdose4u]

Welcome :)

[@Amritanjali]

we can also solve this by taking xor of all the number in the array and the number from 1 to n so final xor value will be xor of missing number and repeated number now we can easily separate this

[@techdose4u]

This will only be valid if numbers in the given array have all elements from 1 to N.

[@madmax2442]

Thank you so much. Took me a day to finally digest this 😅

[@techdose4u]

:)

[@anixanand162]

nice explanation

[@imthchamp]

Thanks for the Video, really detailed, had a doubt though... 6:28, shouldn't the loop start from 1 only as 4 is already there in the LL? like 3->4->2->1-> loop to 4. OR 8:38, that LL would be 1->2->3->4->1-> loop to 2. I am guessing the second one is where a mistake was probably made.... would be great if you can clear this.

[@prodiptamondal1758]

i am having the same confusion for second one

[@meghnasingh9941]

@@prodiptamondal1758 it will go to 4 and so when 4 is pre-existing we can report it as duplicate.

[@omkarrasal1395]

Very nice sirrr.. Thank you so much 🙌🙏

[@techdose4u]

Welcome :)

[@katelynw8392]

Very clear and detailed explanation, thank you

[@techdose4u]

Welcome :)

[@saladmaster3496]

wow, what a beautiful solution

[@techdose4u]

Thanks :)

[@fantasy9960]

great explanation!!!!thank you

[@HimanshuSingh-tu7ik]

thank you for explaining through this question I was struggling on it earlier through floyd detection though it is simple .

[@techdose4u]

Welcome :)

[@quirkyquark99]

Hey what if the first index number is repeated? Cycle won't form then.

[@HimanshuSingh-tu7ik]

@@quirkyquark99 got it, thanks!

[@alexsparrow8614]

your teaching is very well ........... but my doubt is .... in first method(only positive integer) how to work this input = {1,2,3,100,5,100}; becz 100 is grater then array size

[@techdose4u]

Please read the problem well. It's mentioned that values will be in array size range.

[@anandkushwaha01]

I have a doubt regarding the point III, mentioned in the algo. let's say you have an array [1,2,3,4,4]. if you represent this in link list form, it will be link 1->2->3->4 and at it will be a loop. but in cycle first node 1 is not there which is not following the point III. please correct if I misunderstood something here.

[@NomadicShepherd]

So, acc. to array 1 2 3 4 4 we end up generating the self-loop at node 4 and if we follow the tortoise method to detect the starting of the loop we get 4 as result hope that helps.

[@PabitraPadhy]

So, the slow and the fast are not starting from the first node, instead they start from somewhere outside. That outside is basically index 0, of the array. Think like this.. none of the nodes of the linked list points to the item before the first node. x ] -> 1->2->3->4 4 cannot point to x and make a loop, because it's not exactly a node. so, X must be outside the loop always, in out case that's index 0. None, of the array elements are 0, they cannot be that's the constraint. So, this is where you start from.

[@saranyas7629]

Your videos are really nice and it has made me take up leet code challenges continuously. Thank you !! Also can you provide link for Floyd cycle detection algorithm video pls???

[@techdose4u]

That's in the description below. Please check it.

[@sandipsubedi2294]

@@techdose4u I don't see the link.

[@dhruvilbhuptani727]

@@sandipsubedi2294 please wear chasma

[@chetanshrivastava3762]

Very nice explanation..

[@techdose4u]

Thanks

[@rishabhgupta9846]

My code using the first method, successfully submitted int findDuplicate(vector& nums) { int i; for( i=0;i

[@electric336]

9:30 The first element doesn't seem to always be in the loop. Try the list [1,2,4,2,3] .

[@techdose4u]

It is never guaranteed who will be in loop. But the 1st element is never in loop.

[@krystaljinluma]

@@techdose4u why did you say "the first node will always be in the cycle HAVING the repeating element" then? im confused...

[@sharathvenkatesh]

What he meant was the first node is always connected to the cycle component. The first element cannot be in the cycle path since it does not have an incoming edge in the LL representation.

[@HARI-ip4ep]

Searching for this comment

[@HARI-ip4ep]

@@sharathvenkatesh Thank you

[@mathematicalninja2756]

This is pure genius/

[@techdose4u]

:)

[@maths_with_fun8592]

Nice explanation. Thank you for this type of videos.

[@techdose4u]

Welcome

[@yitingg7942]

What am I going to do without you Sir ?

[@techdose4u]

What happened ? 😅

[@yitingg7942]

@@techdose4u Thank you for all the help Sir, I would not be able to survive without you!!

[@techdose4u]

I will always be there. So, you do not need to worry :)

[@yitingg7942]

@@techdose4u Thank you so much Sir, you made me wanna cry..

[@ravishankar9247]

At 14:00 , why did you recreate node-4, I am sorry to say this but you have totally confused me......

[@prathamsharma3502]

does using LL violates the constant space restriction ? Please explain...

[@kaichenghu3826]

I smash the like button then I watch the video

[@techdose4u]

🤣

[@omi_naik]

Hash map would also help in this case, but the problem statement says it requires constant space

[@Moch117]

That’s the whole point

[@shobhitkumar6820]

Sir in the 7:06 part of the video i think by mistake you have made the wrong linked list i.e ypu have made 2 4's instead of showing cycle there.

[@techdose4u]

I have drawn correctly. It is from value to value. Index is just used to get values.

[@shobhitkumar6820]

Sir but are making the repeating element two times instead of just making a cycle there only. In this way i think it will violate the fact that starting of loop is always the start pointer of cycle...plz reply sir

[@shobhitkumar6820]

Okay so you have not used exact cycle detection method but a slight variance of that

[@techdose4u]

I have used exact same cycle detection method with just a change that we need to find the element occuring before intersection point, that is the element pointing to intersection node.

[@shobhitkumar6820]

@@techdose4u thanks sir👍👍

[@saravanan925]

I am getting confused in this point : the 0 index element will never be in a loop. For ex: [1, 4, 3, 2, 1] I hope this forms a loop for 1st element. Correct me if I am wrong

[@persianwaffle]

Hi Saravanan, the indexing starts at zero so what he meant was that since zero is not there in the array you wont get caught up in the first index forever. now you will be directed to some other index from 0th index. this means none of the index will have the index as their value. i.e. index 1 will not have 1 as value, 2 will not have 2 as a value. if it has it means that will be a duplicate element. sorry i am bad at explanation. hope it helps

[@ashfaaqmir7869]

@@persianwaffle not bad but terrible

[@vishalBaid]

If the array have number more than the size of array like size of array let say 4 and array looks like 5,6,6,1, then this solutions(mutable array one) will not work. Correct ?

[@aimanmumtaz3851]

How will you create graph for a={1,3,4,2,2,5} ????

[@vijayj1997]

@TECH DOSE CAN you explain infamous manacher's algorithm

[@techdose4u]

I will, when the time comes :)

[@sriharshasamayamanthula2692]

good explanation sir. But when we take input as [1,3,2,1,1] i get 3 as answer. In this case loop starts at 3. please correct me if am wrong

[@ShreyaSingh-vr9qi]

Awesome explaination

[@techdose4u]

Thanks

[@shobhitkumar6820]

In the next eg also i think you have made the wrong linked list as last node should point to 1 and not 2. Plz correct me if i am wrong

[@Hhtesh]

why didn't you link 2nd 4 to the first 4 in link like you did it for 2 ? 6:55

[@pulkitahuja4750]

Because they are pointed to by the same indexes i.e, 4

[@de-stressmusic432]

Beware: Assumption 4 is wrong. The video shows many lists that are not connected properly. At 12:20, 1 should be connected to a previously appearing 4 in a cycle. Instead, another 4 was created as a mistake. If you connect everything as a cycle, an element at the beginning of a cycle is the duplicate in an array(number 4 in this case) . I spent so much time figuring it out. Assumption 4 should be: The repeated number is the beginning point of the cycle.

[@aryan7069_]

we can just take XOR of all elements

[@yashSharma-pe1dp]

Thanks sir, your videos are gr8 as always.

[@techdose4u]

Thanks

[@ayushraj-zb6sv]

do interviewers expect Floyd cycle detection algo for this question ? Is't it more like just remembering the solution .. i mean its not intuitive ?

[@techdose4u]

It's not intuitive, that's why I explained it thoroughly. They might expect. According to how requirements are increasing day by day, who knows. It depends on interviewer as a person. If he is logical enough then he should not expect but again, candidates are setting new standards and so they might expect.

[@ayushraj-zb6sv]

@@techdose4u oh i see,anyways i understood the solution..so no worries :)

[@himanshugupta7647]

hi @TECH DOSE i have just started learning dsa is 8 months enough to get into amazon

[@techdose4u]

Yes. But you need to give the best preparation you can for cracking it.

[@random2402]

Which software do you use to annotate on the screen? Please reply...

[@vikramgara]

In the first solution(array mutable), the solution does not work if the number is repeated odd number of times.

[@mdisi5967]

We don't care about how many times the element was repeated but we want to know which one was repeated, so we stop on the first repetition of the element.

[@rishabhgupta9846]

int findDuplicate(vector& nums) { int i; for( i=0;i

[@lomoyang3034]

Where I can find the mathematic prof for the first method?

[@techdose4u]

Stackoverflow

[@charlesbickham6604]

Could you add the numbers 1-n in the first loop and then in the second iterate through the array subtracting the values. Then you return -1*ans

[@arijitroy8390]

why is do-while used and not while?

[@shivanigupta_19]

you are really wonderful :)

[@techdose4u]

Thanks 😊

[@shivanigupta_19]

@@techdose4u ❤🎉🤩

[@Supercool7042]

@TECH DOSE ladki ka cmnt dekh k pighal Gaya 😅😅😅

[@shivanigupta_19]

@@Supercool7042 don't create negative environment.

[@Supercool7042]

@SHIVANI GUPTA OK MADAM 👍👍🙏🙏

[@hemachandrakumar9952]

Why not xor the array elements with numbers 1-n?

[@theskyguy126]

8:00 Pigeonhole principle

[@krystaljinluma]

10:35 I don't understand why you said "the first node will always be in the cycle HAVING the repeating element" - what does this mean? Do you mean the first node will NEVER be in the cycle? because you said it doesn't have incoming edges?

[@krystaljinluma]

if we have [2,3,4,1,1], the linked list will be 2->4->1->3->1 (1points back to 3), and 2 is not anywhere in the cycle?

[@punittripathi5461]

A little slower explaination pace than current would be appreciated .

[@techdose4u]

That would make video longer and probably I might not get good audience retention pecentage wise.

[@anirudhreddybasani3555]

@@techdose4u your pace is alright.

[@charan775]

6:50 you are not making extra node for 2 since it is already visited. Then why did you make extra node for 4?

[@aditya234567]

He has drawn correctly. It is from value to value. Index is just used to get values.

[@bisatisrilatha7957]

bro if we have to find element before fast==slow why return fast???????????????????????????????

[@madhupatel4484]

Mutable immutable??

[@akhil3588]

Mutable- means you can change the elements in given array.

[@jatinbhatoya8420]

sir aapne jo 1st trick btayi hai vo sahi nhi hai. take array as 1 2 3 4 5 1 . ur first trick is not giving correct answer for this array.

[@RavisCodeDiary]

It's working, 1 -2 -3 -4 -5 -1 then at index 1 i.e. -2 which is negative. So 1 is repeating.