Find the duplicate number (LeetCode 287) | Full solution with different methods | Study Algorithms
ฝัง
- เผยแพร่เมื่อ 21 ก.ค. 2024
- To see more videos like this, you can buy me a coffee: www.buymeacoffee.com/studyalg...
You are given an array of integers, that have all unique values except one integer that may be duplicated more than 2 times. You just need to return this value. Seems like a very easy problem but it offers you a lot of scope. There can be several different solutions possible based upon the requirements. This video explores a brute force method, a time efficient method and a space efficient method. All along with easy to understand visuals and animations.
Chapters:
00:00 - Intro
01:27 - Problem statement and description
03:26 - Brute Force approach to find the duplicate number
05:13 - Find the duplicate number using sorting
07:07 - Find the duplicate number using a HashSet
10:16 - Time and space efficient solution to find duplicate
14:14 - Dry-run of code
16:50 - Final Thoughts
Actual problem on LeetCode: leetcode.com/problems/find-th...
📚 Links to topics I talk about in the video:
Detect Cycle Start in Linked List: • Linked List Cycle 2 (L...
Linked List Introduction: • Linked List Data Struc...
Brute Force Method: • Brute Force algorithms...
Quick Sort: • Quick Sort super easy ...
Time Complexity: • Big O Notation Simplif...
Playlist on Linked Lists: • Linked Lists
📘 A text based explanation is available at: studyalgorithms.com
Code on Github: github.com/nikoo28/java-solut...
Test-cases on Github: github.com/nikoo28/java-solut...
📖 Reference Books:
Starting Learn to Code: amzn.to/36pU0JO
Favorite book to understand algorithms: amzn.to/39w3YLS
Favorite book for data structures: amzn.to/3oAVBTk
Get started for interview preparation: amzn.to/39ysbkJ
🎥 My Recording Gear:
Recording Light: amzn.to/3pAqh8O
Microphone: amzn.to/2MCX7qU
Recording Camera: amzn.to/3alg9Ky
Tablet to sketch and draw: amzn.to/3pM6Bi4
Surface Pen: amzn.to/3pv6tTs
Laptop to edit videos: amzn.to/2LYpMqn
💻 Get Social 💻
Follow on Facebook at: / studyalgos
Follow on Twitter at: / studyalgorithms
Follow on Tumblr at: / studyalgos
Subscribe to RSS feeds: studyalgorithms.com/feed/
Join fan mail: eepurl.com/g9Dadv
#leetcode #programming #linkedlists
Your explanation is amazing. Thank you so much for putting so much effort into your video. : D
Bhai ka padhaya h...itne pyar aur patience se...thank you so much❤
glad it was helpful :)
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 👍
really like your explanation style and diagrams!
Pure GOLD ! Keep it up brother.
I think you worth my time great explanation bro . Thanks for your efforts and guidance
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 ..❤❤
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)..
your way of explanation creates and makes interest to learn the solutions of the problem sir 👌
Your explanation style is so good.
Great explanations. Thanks you!
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).
Awesome explanation, thank you!
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.
can you please explain how to solve this using binary search
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 ?
a comprehensive solution 👍
Everytime when the question says "Duplicate" I follow Hashset. But this Logic is better. Thanks
I have found very helpful videos 🎉
great explanation men
Great job bro.
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.
amazing!!
thank you bro
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
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.
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
perfect in all side
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.
Nikil, Suppose 3rd & 4th position is 25,25 , how will work based on index?
Give me the complete test case
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: th-cam.com/video/95ZfuoSAUPI/w-d-xo.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
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
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
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
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.❤
not allowed to use extra space, using linked list or hash map would not work
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.
i did not understand fast=nums[nums[fast]] .if nums[fast] is 3?
then fast = nums[3]
Why do we need a slow pointer and a fast pointer? Would we not be able to reach the answer if we have both pointers going at the same speed and just see when they both meet? Essentially just doing the second portion of your code.
just try an example and see how the pointers behave, I am sure you will get the answer yourself 😄
the good old pen/paper works miracles
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!
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.
th-cam.com/video/95ZfuoSAUPI/w-d-xo.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
Impressive
What if the value grater than array length?
look at the problem constraints on leetcode
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. :)
what a solution bhiya
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
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
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.
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 🙏👍
u are awesome
Heya! Great explaination as usual.
I'm just having one concern, if I search for any problem on TH-cam 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 TH-cam 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.
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.
We can also solve this using Binary Search
nice
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?
please make recursion playlist
will do that soon
its cool
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 🤭
amazing..keep going
Nikhil bro 👌
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.
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 🙂
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]
in Leetcode, this solution results in TLE
checkout the solution I have in video description/dry-run of code. The code passes successfully :)
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