This is the best of all and I nearly spent 30 mins of time to search for a best one and I sticked with this . Thanks Brother btwn your explanation and presentation was perfect.🙌Keep teaching and sharing.
trick here is to think why in question it was actually said the number present in the array is 1 to N-1. then we can come up with this logic. Agar starting mein kuch aur hota 14 to lag jate is alogrithm ke, its not applicable
brother the detailing in this video and your way of teaching is just mind blowing, until now i was feeling dsa is boring but this has just made me interested all over again. Thanks a ton ! Love!!
Awesome explain the last one was supper ... Yes we can do that with hashmap just store the count of value as value and index as value in hashmap and then iterated over array and check the count of value in hashmap is greater than 1 or not if yes , just return the array value. TC is O(n) and SC is O(n)..
hey bro can you please explain me ; how fast pointer moving two step and how slow pointer moving 1 step; according to code it can jump randomly. like at 14:15 if slow pointer pointing on 2nd index then in next loop slow pointer will point 4th index its just jump the 3rd index.
Sir, your voice and clear cut communication skills are awesome...you have explained the driver code also.. with the original code...! Those who Dont know the coding.. they can also can understand.. So, thank you very much for providing this good quality videos on the youtube ..❤❤
Why is the repeated number guaranteed to be reachable from index 0? Why is it guaranteed to: 1. Have a loop, which includes the repeated number? 2. The repeated number starts the loop? Why it can't be in the middle of the loop?
Both the questions are really good. I gave a reference to the original problem that explores the proof. Linked List Cycle 2. The link is available in the video description. ruclips.net/video/95ZfuoSAUPI/видео.html
Let n be the size of the array. Assume all elements are 1 to n-1 inclusive. Starting from index 0, we construct a diagraph G in that manner. Every vertex in G has exactly one outgoing edge. Consider a walk from vertex 0. By the pigeonhole principle this walk will eventually reach a vertex for the second time, creating a directed cycle in G. QED
but lets take [1,2,3,4,5,5] as the array ,, now slow =nums[0] which is 1 and fast=nums[nums[fast]] which is is 2 so slow is at sitting at first node and fast is siting at 2nd node . in this case now fast is two step ahead with slow ?
Heya! Great explaination as usual. I'm just having one concern, if I search for any problem on RUclips which you have solved I don't get suggestion for you channel easily. Even after adding the end phrases as '..by study algorithms' I don't get the result. (I have subscribed you channel) Many of the times I have put the exact string which you have given as a title to the video or I have to search for channel then playlist and then video. One reason might be is it always suggest the videos with more views and another reason which I suspect is the name of the channel. Bcz others also put phrase like ' study algorithm' in their videos either in title or tags. My humble suggestion is to go digger into RUclips algorithm and figure out something which will give us results (e.g adding all combinations of tags.) Your explanations are way better and I really want them to reach more n more learners. Thanks! 😊
Yes I am also agree with with this point. I also don't get the results and suggestions to your videos easily. And I also think the name of the channel can be one reason because everyone puts 'study' / 'algorithms' in their videos.
Thanks firstly for both of your suggestions 🙂. I am actually working on a new channel name that could help to uniquely identify results. Support from followers like you is really motivating and pushes me to work harder. Thanks once again, I will try to get those changes as soon as time permits.
Is the hash set solution really O(n) time complexity? For every element, you have to check whether it's in the set, which takes O(n). Meaning it should be O(n*n) worst case.
Soooo I have watched this video multiple times and have looked at the question you show in the beginning of the video. Though I understand what you’re doing with using an index to identify duplicates what I don’t understand how this would work based off your question without knowing the range of numbers in the array. Your example uses something like this: [2,4,1,6,3,1]. How will this solution work with an array like this based off the question?[3,16,1,4,2,1].
read the problem statement again. "Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive." So for your test case when there is a 16, there should be atleast 16 elements in the array. Always read the problem constraints...they do give out a very good hint :)
The question mentions that You must solve the problem without modifying the array nums and uses only constant extra space, isn't sorting the array and using hashset violate this??
@@nikoo28general two pointer ,but not single video a playlist comprising all questions, because the two pointer playlist is not available on any channels
That is more or less based on finding a loop in a linked list. If you recall that problem, we apply the same concept over there. So as soon as the problem translates to a same structure, we apply the fast and slow pointer approach
@@nikoo28 This algo is called Floyd's Tortoise. But I have found 2 problems with it. 1. If the first element(0th index) is has 0. Then 0 will keep pointing to itself and will give us 0 as result. 2. If two indexes have each other as their value. Then they will keep pointing to each other. For these two cases i am not getting the right answer. Please suggest something.
@@nikoo28 Thanks for clarification. But then this looks like a Trick question if the target to get this particular solution. Loving your videos by the way.❤
One question: after you find the point slow and fast met, why are you setting the slow as 0 again? I feel like if you set slow as 0 and fast at the point where fast and slow meets, are they not supposed to meet with each other every again?
From the cidoe you reference: we got the equation (n_2 - 2n_1)L = x + y. This equation alone indicates the spot when the fast and the slow meet together is special. On the right side, x+ y is the distance fast will travel. On the left side, (n_2 - 2n_1)L is the distance where the slow will travel because the slow is already in the loop and its traveling distance must be a constant times L. Am I correct? By the way, I appreciate that you responded to me that quickly. Thanks a ton. @@nikoo28
With the link list solution what do you do when the element corresponds to an index out of bounds? Eg. 2,5,8,8,4. The problem statement only mentions "positive integers". It does not say anything about an upper bound for the elements? PS: im refering to the statement you showed in the video which may be different from Leetcode's original statement.
does the hashset solution have O(n) complexity as for each element we are also checking the set to check if it occured before in the set. as in the worst case if the repeating element occurs in the end of the array you have to insert n-1 element into the set and iterate through the set for all these n-1 elements then that tc would be about O(n2).
XOR works when all numbers are duplicated, except one. example: you can XOR all numbers in array [ 1, 1, 5, 5, 7, 6, 7, 6, 4 ] The answer will be 4 in this case
ahh this problem has me so dizzy. just starting with medium problems today. and using the array like its a linked list is just weird to me. but it works well it seems.
there will be always a duplicate element and according to problem statement, in array of (n+1) length, elements will be from [0 , n]. So take any element from array(say n), we will have it in index also. Sorry for poor wording, but try to get a valid testcase and you will understand. (yours in not valid as array length is 2, so max element in it can be only 1 and obviously you don't have a duplicate in your array)
we did not create the linked list here, we just assumed the array to be a linked list, we did the linked list like operations on the array. here the ListNode can be assumed as the 'value' is the value of the element, and it's 'next' is actually the nums[value].
That loop will help the fast pointer to catch the slow pointer. This approach is borrowed from detecting a loop in a linked list. Please also watch that video…and everything will be definitely clear.
i wouldn't say that you will never be able to solve them. The thing is you will start identifying patterns...and after a while you will be able to realize if the problem is actually challenging or just tricky. Talking about an interview, if you just walk through the thought process and come up with all possible ways to attack, the interviewer will be happy...that you know all these approaches. So, coming back to your original question...if you find such a problem in an interview...don't just sit quiet and try to figure out a solution. Keep talking about all the approaches you have in mind...this will surely help the interviewer to assess you better. They can nudge you in the right direction.
if the element of the array is 0 to n or 1 to n we can do cyclic sort which takes O(n) time complexity and O(1) space complexity for more information on cyclic sort do check kunal kushawaha video on dsa java bootcamp
16:26 I think you don't know what to do. You're saying we have to move the pointers to the beginning. Actually, you have to move only one of the pointers to the beginning.
as I say in the video...we use the concept of finding the cycle in a linked list, which works on the hare and tortoise algorithm. Find the link in the description to understand how that two pointer approach works. :)
i feel like the question is specifically made according to ur solution ...thank god i watched it way before my interview....not a good solution! Subscribed but then unsubscribed in the end
read the problem statement correctly. the array integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive. so there will never be a case when the integer is greater than the array size.
![ARGENTINA vs. BOLIVIA [6-0] | RESUMEN | ELIMINATORIAS SUDAMERICANAS | FECHA 10](http://i.ytimg.com/vi/C3wPtKNbAOA/mqdefault.jpg)
This is the best of all and I nearly spent 30 mins of time to search for a best one and I sticked with this . Thanks Brother btwn your explanation and presentation was perfect.🙌Keep teaching and sharing.
Glad you liked it!
There is another solution which is change the number to negative based on the index value. It's also o(n).
trick here is to think why in question it was actually said the number present in the array is 1 to N-1. then we can come up with this logic. Agar starting mein kuch aur hota 14 to lag jate is alogrithm ke, its not applicable
yep, these are the problem contraints
brother the detailing in this video and your way of teaching is just mind blowing, until now i was feeling dsa is boring but this has just made me interested all over again. Thanks a ton ! Love!!
thanks for the attention to detail :)
The way you explain is amazing,,, keep posting more videos, Looking for more easy and medium leetcode problems
Sure 👍
Awesome explain the last one was supper ... Yes we can do that with hashmap just store the count of value as value and index as value in hashmap and then iterated over array and check the count of value in hashmap is greater than 1 or not if yes , just return the array value. TC is O(n) and SC is O(n)..
Bhai ka padhaya h...itne pyar aur patience se...thank you so much❤
glad it was helpful :)
The way you explain is just awesome.
hey bro can you please explain me ;
how fast pointer moving two step and how slow pointer moving 1 step;
according to code it can jump randomly.
like at 14:15 if slow pointer pointing on 2nd index then in next loop slow pointer will point 4th index its just jump the 3rd index.
Sir, your voice and clear cut communication skills are awesome...you have explained the driver code also.. with the original code...! Those who Dont know the coding.. they can also can understand.. So, thank you very much for providing this good quality videos on the youtube ..❤❤
Why is the repeated number guaranteed to be reachable from index 0?
Why is it guaranteed to:
1. Have a loop, which includes the repeated number?
2. The repeated number starts the loop? Why it can't be in the middle of the loop?
Both the questions are really good. I gave a reference to the original problem that explores the proof. Linked List Cycle 2.
The link is available in the video description.
ruclips.net/video/95ZfuoSAUPI/видео.html
Let n be the size of the array. Assume all elements are 1 to n-1 inclusive. Starting from index 0, we construct a diagraph G in that manner. Every vertex in G has exactly one outgoing edge. Consider a walk from vertex 0. By the pigeonhole principle this walk will eventually reach a vertex for the second time, creating a directed cycle in G.
QED
Your explanation style is so good.
Amazing video explanation🙌
Everytime when the question says "Duplicate" I follow Hashset. But this Logic is better. Thanks
but lets take [1,2,3,4,5,5] as the array ,, now slow =nums[0] which is 1 and fast=nums[nums[fast]] which is is 2 so slow is at sitting at first node and fast is siting at 2nd node . in this case now fast is two step ahead with slow ?
Your explanation is amazing. Thank you so much for putting so much effort into your video. : D
Pure GOLD ! Keep it up brother.
really like your explanation style and diagrams!
Great explanations. Thanks you!
Heya! Great explaination as usual.
I'm just having one concern, if I search for any problem on RUclips which you have solved I don't get suggestion for you channel easily. Even after adding the end phrases as '..by study algorithms' I don't get the result. (I have subscribed you channel)
Many of the times I have put the exact string which you have given as a title to the video or I have to search for channel then playlist and then video.
One reason might be is it always suggest the videos with more views and another reason which I suspect is the name of the channel.
Bcz others also put phrase like ' study algorithm' in their videos either in title or tags.
My humble suggestion is to go digger into RUclips algorithm and figure out something which will give us results (e.g adding all combinations of tags.)
Your explanations are way better and I really want them to reach more n more learners. Thanks! 😊
Yes I am also agree with with this point. I also don't get the results and suggestions to your videos easily.
And I also think the name of the channel can be one reason because everyone puts 'study' / 'algorithms' in their videos.
Thanks firstly for both of your suggestions 🙂. I am actually working on a new channel name that could help to uniquely identify results.
Support from followers like you is really motivating and pushes me to work harder.
Thanks once again, I will try to get those changes as soon as time permits.
Is the hash set solution really O(n) time complexity? For every element, you have to check whether it's in the set, which takes O(n). Meaning it should be O(n*n) worst case.
the problem constraints avoid the worst case time complexity, check the leetcode link
your way of explanation creates and makes interest to learn the solutions of the problem sir 👌
not allowed to use extra space, using linked list or hash map would not work
Soooo I have watched this video multiple times and have looked at the question you show in the beginning of the video. Though I understand what you’re doing with using an index to identify duplicates what I don’t understand how this would work based off your question without knowing the range of numbers in the array. Your example uses something like this: [2,4,1,6,3,1]. How will this solution work with an array like this based off the question?[3,16,1,4,2,1].
read the problem statement again.
"Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive."
So for your test case when there is a 16, there should be atleast 16 elements in the array. Always read the problem constraints...they do give out a very good hint :)
@@nikoo28 where is this question in your video? Please reread the question you showed us in the video.
check the video description for actual problem
I think you worth my time great explanation bro . Thanks for your efforts and guidance
what a solution bhiya
Nikil, Suppose 3rd & 4th position is 25,25 , how will work based on index?
Give me the complete test case
a comprehensive solution 👍
Bhaiya isme sum of array and sum of number of elements n*n+1/2 and then subtract it we can get the answer but I got run time error how do I resolve it
check the code in the video description. That works perfectly.
The question mentions that You must solve the problem without modifying the array nums and uses only constant extra space, isn't sorting the array and using hashset violate this??
If you look at the last method I talk about, that is the most efficient and does not modify the array. Uses constant space too. :)
your explanation is best,can you make a playlist of two pointers approach
Two pointer approach for this problem or a two pointer approach in general??
@@nikoo28general two pointer ,but not single video a playlist comprising all questions, because the two pointer playlist is not available on any channels
Please explain the reason behind that "fast and slow" concept that you used.
That is more or less based on finding a loop in a linked list. If you recall that problem, we apply the same concept over there.
So as soon as the problem translates to a same structure, we apply the fast and slow pointer approach
@@nikoo28 This algo is called Floyd's Tortoise. But I have found 2 problems with it.
1. If the first element(0th index) is has 0. Then 0 will keep pointing to itself and will give us 0 as result.
2. If two indexes have each other as their value. Then they will keep pointing to each other.
For these two cases i am not getting the right answer. Please suggest something.
thank you so much
So this optimized solution will work only when the numbers are in the range (1- n) ?
That is the constraint of the problem
@@nikoo28 Thanks for clarification. But then this looks like a Trick question if the target to get this particular solution. Loving your videos by the way.❤
Awesome explanation, thank you!
amazing!!
thank you bro
One question: after you find the point slow and fast met, why are you setting the slow as 0 again? I feel like if you set slow as 0 and fast at the point where fast and slow meets, are they not supposed to meet with each other every again?
Have a look at: ruclips.net/video/95ZfuoSAUPI/видео.htmlsi=fL17cmRkqyjattlJ
This explains the mathematical proof
From the cidoe you reference: we got the equation (n_2 - 2n_1)L = x + y. This equation alone indicates the spot when the fast and the slow meet together is special. On the right side, x+ y is the distance fast will travel. On the left side, (n_2 - 2n_1)L is the distance where the slow will travel because the slow is already in the loop and its traveling distance must be a constant times L. Am I correct? By the way, I appreciate that you responded to me that quickly. Thanks a ton. @@nikoo28
perfect in all side
With the link list solution what do you do when the element corresponds to an index out of bounds? Eg. 2,5,8,8,4.
The problem statement only mentions "positive integers". It does not say anything about an upper bound for the elements?
PS: im refering to the statement you showed in the video which may be different from Leetcode's original statement.
this is a direct solution to the problem available on leetcode, so I would assume we are taking the same constraints.
does the hashset solution have O(n) complexity as for each element we are also checking the set to check if it occured before in the set. as in the worst case if the repeating element occurs in the end of the array you have to insert n-1 element into the set and iterate through the set for all these n-1 elements then that tc would be about O(n2).
The best case time complexity will be with the last method
great explanation men
Hi bro, the problem constraint is nums[I] of value 1 to n, why can't we achieve using xor operator
XOR works when all numbers are duplicated, except one.
example: you can XOR all numbers in array [ 1, 1, 5, 5, 7, 6, 7, 6, 4 ]
The answer will be 4 in this case
I have found very helpful videos 🎉
Great job bro.
Impressive
ahh this problem has me so dizzy. just starting with medium problems today. and using the array like its a linked list is just weird to me. but it works well it seems.
can you please explain how to solve this using binary search
i did not understand fast=nums[nums[fast]] .if nums[fast] is 3?
then fast = nums[3]
My Hashing technique got accepted on the leetcode
the best optimal approach is lil bit tricky
Sure, the hashing technique gets accepted…but thinking out different solutions never hurt. A good exercise for your brain 😄
@@nikoo28 exactly 🤭
Let’s say input was [2, 1] wouldn’t we go out of bounce after the first iteration?
there will be always a duplicate element and according to problem statement, in array of (n+1) length, elements will be from [0 , n]. So take any element from array(say n), we will have it in index also. Sorry for poor wording, but try to get a valid testcase and you will understand. (yours in not valid as array length is 2, so max element in it can be only 1 and obviously you don't have a duplicate in your array)
@@berzgar6927 ah I See there will always be a dup. problem ranges from [1,n] inclusive btw
@berzgar6927 is absolutely correct
Can anyone tells me that how this solution ends up in O(1) space complexity?
Because, creation of linked list would take O(n) space?
No?
we did not create the linked list here, we just assumed the array to be a linked list, we did the linked list like operations on the array.
here the ListNode can be assumed as the 'value' is the value of the element, and it's 'next' is actually the nums[value].
Absolutely correct
@@rishidangi2978 Okay got your point!
Last wala while loop kyu lgya kuch clear nahi hua can u pls explain it here
That loop will help the fast pointer to catch the slow pointer.
This approach is borrowed from detecting a loop in a linked list. Please also watch that video…and everything will be definitely clear.
Let me know if you still face issues
Thank you very much bahiya not its 101% clear nd i am feeling good after successfully understand this and also thanks for replying 🙏👍
please make recursion playlist
will do that soon
What if the number is more than the index number than it says out of bound then how
That will not happen with the given problem constraints
We can also solve this using Binary Search
ye sochunga kaise main interview me?
practice, practice and a lot of more practice.
@@nikoo28 hello nikhil , that is true
but i am SDE3 , and still feel kuchh questions trivial hi hain , agar nahi kiye to nahi honge.
Do you agree?
i wouldn't say that you will never be able to solve them. The thing is you will start identifying patterns...and after a while you will be able to realize if the problem is actually challenging or just tricky. Talking about an interview, if you just walk through the thought process and come up with all possible ways to attack, the interviewer will be happy...that you know all these approaches.
So, coming back to your original question...if you find such a problem in an interview...don't just sit quiet and try to figure out a solution. Keep talking about all the approaches you have in mind...this will surely help the interviewer to assess you better. They can nudge you in the right direction.
u are awesome
if the element of the array is 0 to n or 1 to n we can do cyclic sort which takes O(n) time complexity and O(1) space complexity for more information on cyclic sort do check kunal kushawaha video on dsa java bootcamp
any topics you got in mind?
16:26 I think you don't know what to do.
You're saying we have to move the pointers to the beginning. Actually, you have to move only one of the pointers to the beginning.
you are absolutely correct. Sorry for the mistake while recording...but glad you got the concept correct 🙂
Floyd’s Tortoise and Hare algorithm
Why we need to move the fast pointer twice of slow in the do while loop?
as I say in the video...we use the concept of finding the cycle in a linked list, which works on the hare and tortoise algorithm. Find the link in the description to understand how that two pointer approach works. :)
@@nikoo28 Thanks for the quick response.
What if the value grater than array length?
look at the problem constraints on leetcode
nice
in Leetcode, this solution results in TLE
checkout the solution I have in video description/dry-run of code. The code passes successfully :)
its cool
just xor all the numbers and xor again 1 ... n. You will get your ans
Your solution will not work with an array like [1, 2, 2, 2, 2, 5]
Nikhil bro 👌
amazing..keep going
i feel like the question is specifically made according to ur solution ...thank god i watched it way before my interview....not a good solution! Subscribed but then unsubscribed in the end
suggest me a better approach please. :)
your time and space efficient solution will fail. if some of the value of array is greater than array length
read the problem statement correctly. the array integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.
so there will never be a case when the integer is greater than the array size.
With n we have a problem, that's already out of bounds.
@@Grassmpl There's a constraint nums.length == n + 1. Meaning n is always < nums.length. So n will never be out of bounds.
ujwal gamer zindabad