Find the duplicate number (LeetCode 287) | Full solution with different methods | Study Algorithms

Подписаться 40 тыс.

Просмотров 33 тыс.

50% 1

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

Опубликовано:

7 июл 2024

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 123

@sameersayyad6170 8 месяцев назад

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

@nikoo28 8 месяцев назад

thanks for the attention to detail :)

@aakarshachug5342 Год назад

Your explanation is amazing. Thank you so much for putting so much effort into your video. : D

@purplewombat6735 2 года назад

really like your explanation style and diagrams!

@jaganchowhaan9648 2 года назад

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.

@nikoo28 2 года назад

Glad you liked it!

@eile4219 Год назад

There is another solution which is change the number to negative based on the index value. It's also o(n).

@udaykulkarni5639 2 года назад

Pure GOLD ! Keep it up brother.

@salmarafiq7695 Год назад

The way you explain is amazing,,, keep posting more videos, Looking for more easy and medium leetcode problems

@nikoo28 Год назад

Sure 👍

@user-kc4yv5kt3j 8 месяцев назад

Great explanations. Thanks you!

@VishalTrivediB 2 года назад

Awesome explanation, thank you!

@prabirmaity4529 Год назад

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

@padmapriya5423 Год назад

your way of explanation creates and makes interest to learn the solutions of the problem sir 👌

@movocode 3 месяца назад

Your explanation style is so good.

@invinciblevikas9553 Год назад

I think you worth my time great explanation bro . Thanks for your efforts and guidance

@BigBangBong1 3 месяца назад

The way you explain is just awesome.

@mohammadnazrulislam-iz2xc 2 месяца назад

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.

@vcs649 6 месяцев назад

a comprehensive solution 👍

@Sanjay_beliver 3 месяца назад

great explanation men

@omarrashedsizan8723 Год назад

Great job bro.

@rajeshpaithari7320 3 месяца назад

Everytime when the question says "Duplicate" I follow Hashset. But this Logic is better. Thanks

@mock1112 Год назад

I have found very helpful videos 🎉

@user-jr1vc3cc6c Год назад

amazing!!

@Grassmpl 10 месяцев назад

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.

@nikoo28 10 месяцев назад

this is a direct solution to the problem available on leetcode, so I would assume we are taking the same constraints.

@shivaakrish Год назад

can you please explain how to solve this using binary search

@AffairWithGeo 11 месяцев назад

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

@nikoo28 11 месяцев назад

yep, these are the problem contraints

@emma_anime 6 дней назад

thank you bro

@I_W23 3 месяца назад

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

@nikoo28 3 месяца назад

The best case time complexity will be with the last method

@user-zh1ok2pf2z Год назад

perfect in all side

@fast7rememberIT Месяц назад

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 ?

@developerUtkarsh 8 месяцев назад

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

@nikoo28 7 месяцев назад

check the code in the video description. That works perfectly.

@lonen3rd 9 месяцев назад

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.

@nikoo28 8 месяцев назад

the problem constraints avoid the worst case time complexity, check the leetcode link

@DavidDLee Год назад

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?

@nikoo28 Год назад

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. ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-95ZfuoSAUPI.html

@Grassmpl 10 месяцев назад

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

@miheerhasabnisd3930 Год назад

your explanation is best,can you make a playlist of two pointers approach

@nikoo28 Год назад

Two pointer approach for this problem or a two pointer approach in general??

@miheerhasabnisd3930 Год назад

@@nikoo28general two pointer ,but not single video a playlist comprising all questions, because the two pointer playlist is not available on any channels

@tonymontana9221 4 месяца назад

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?

@nikoo28 4 месяца назад

Have a look at: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-95ZfuoSAUPI.htmlsi=fL17cmRkqyjattlJ This explains the mathematical proof

@tonymontana9221 4 месяца назад

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

@shraddhapande1183 2 года назад

Heya! Great explaination as usual. I'm just having one concern, if I search for any problem on RU-vid 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 RU-vid 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! 😊

@ajmera8783 2 года назад

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.

@nikoo28 2 года назад

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.

@udayrajvadeghar8555 5 месяцев назад

what a solution bhiya

@Satishsingh-yc9bs 2 месяца назад

So this optimized solution will work only when the numbers are in the range (1- n) ?

@nikoo28 2 месяца назад

That is the constraint of the problem

@Satishsingh-yc9bs 2 месяца назад

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

@kavinkavin3525 5 дней назад

Impressive

@ragupathia2316 2 месяца назад

Nikil, Suppose 3rd & 4th position is 25,25 , how will work based on index?

@nikoo28 Месяц назад

Give me the complete test case

@nandhakumarkr3147 4 месяца назад

Hi bro, the problem constraint is nums[I] of value 1 to n, why can't we achieve using xor operator

@nikoo28 3 месяца назад

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

@myemailis9248 8 месяцев назад

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.

@nikoo28 7 месяцев назад

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

@zariz7219 Год назад

Why we need to move the fast pointer twice of slow in the do while loop?

@nikoo28 Год назад

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

@zariz7219 Год назад

@@nikoo28 Thanks for the quick response.

@parthmodi2028 5 месяцев назад

u are awesome

@harshpalsingh1145 Год назад

Please explain the reason behind that "fast and slow" concept that you used.

@nikoo28 Год назад

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

@harshpalsingh1145 Год назад

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

@amanprajapati3417 Год назад

My Hashing technique got accepted on the leetcode the best optimal approach is lil bit tricky

@nikoo28 Год назад

Sure, the hashing technique gets accepted…but thinking out different solutions never hurt. A good exercise for your brain 😄

@amanprajapati3417 Год назад

@@nikoo28 exactly 🤭

@honey-xr5kp 3 месяца назад

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.

@johnsoto7112 9 месяцев назад

Let’s say input was [2, 1] wouldn’t we go out of bounce after the first iteration?

@berzgar6927 9 месяцев назад

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)

@johnsoto7112 9 месяцев назад

@@berzgar6927 ah I See there will always be a dup. problem ranges from [1,n] inclusive btw

@nikoo28 8 месяцев назад

@berzgar6927 is absolutely correct

@prabhatkumarsingh3073 7 месяцев назад

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

@nikoo28 7 месяцев назад

any topics you got in mind?

@abdulrehmanamer4252 3 месяца назад

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?

@rishidangi2978 3 месяца назад

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

@nikoo28 3 месяца назад

Absolutely correct

@abdulrehmanamer4252 3 месяца назад

@@rishidangi2978 Okay got your point!

@saimani6410 7 месяцев назад

What if the number is more than the index number than it says out of bound then how

@nikoo28 6 месяцев назад

That will not happen with the given problem constraints

@adityakumarsingh8406 3 месяца назад

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

@nikoo28 3 месяца назад

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

@heyneisha3816 7 дней назад

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

@nikoo28 6 дней назад

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

@heyneisha3816 6 дней назад

@@nikoo28 where is this question in your video? Please reread the question you showed us in the video.

@gauravbanerjee2898 10 месяцев назад

We can also solve this using Binary Search

@rudrajitpaul4088 8 дней назад

i did not understand fast=nums[nums[fast]] .if nums[fast] is 3?

@nikoo28 7 дней назад

then fast = nums[3]

@travelnlearn 2 года назад

nice

@mr_who3641 8 месяцев назад

What if the value grater than array length?

@nikoo28 8 месяцев назад

look at the problem constraints on leetcode

@mdshafiuddin1234 9 месяцев назад

please make recursion playlist

@nikoo28 8 месяцев назад

will do that soon

@vlogsaryan2540 Год назад

Last wala while loop kyu lgya kuch clear nahi hua can u pls explain it here

@nikoo28 Год назад

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.

@nikoo28 Год назад

Let me know if you still face issues

@vlogsaryan2540 Год назад

Thank you very much bahiya not its 101% clear nd i am feeling good after successfully understand this and also thanks for replying 🙏👍

@shubhamsonar2930 2 года назад

amazing..keep going

@sumitkumbhkarn 8 месяцев назад

its cool

@samalashivasurya5574 Год назад

Nikhil bro 👌

@prabhavagrawal1712 2 года назад

just xor all the numbers and xor again 1 ... n. You will get your ans

@nikoo28 2 года назад

Your solution will not work with an array like [1, 2, 2, 2, 2, 5]

@akashdey1497 Год назад

in Leetcode, this solution results in TLE

@nikoo28 Год назад

checkout the solution I have in video description/dry-run of code. The code passes successfully :)

@sanchitbatra4431 4 месяца назад

ye sochunga kaise main interview me?

@nikoo28 3 месяца назад

practice, practice and a lot of more practice.

@sanchitbatra4431 3 месяца назад

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

@nikoo28 3 месяца назад

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.

@shishir-kon 3 месяца назад

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.

@nikoo28 3 месяца назад

you are absolutely correct. Sorry for the mistake while recording...but glad you got the concept correct 🙂

@imasunflowerlilfunny3353 9 месяцев назад

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

@nikoo28 8 месяцев назад

suggest me a better approach please. :)

@deepakkansal9112 Год назад

ujwal gamer zindabad

@syedshahzaibzafar2422 2 года назад

your time and space efficient solution will fail. if some of the value of array is greater than array length

@nikoo28 2 года назад

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.

@Grassmpl 10 месяцев назад

With n we have a problem, that's already out of bounds.

@lonen3rd 9 месяцев назад

@@Grassmpl There's a constraint nums.length == n + 1. Meaning n is always < nums.length. So n will never be out of bounds.