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

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

📚 Links to topics I talk about in the video:

📖 Reference Books:

🎥 My Recording Gear:

💻 Get Social 💻

#leetcode #programming #linkedlists

[pbsojxk]

Bhai ka padhaya h...itne pyar aur patience se...thank you so much❤

[aakarshachug]

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

[purplewombat]

really like your explanation style and diagrams!

[sameersayyad]

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

[salmarafiq]

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

[jaganchowhaan]

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.

[invinciblevikas]

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

[padmapriya]

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

[srikavyaswarna]

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

[prabirmaity]

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

[rajeshpaithari]

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

[AffairWithGeo]

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

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

[shivaakrish]

can you please explain how to solve this using binary search

[Grassmpl]

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.

[miheerhasabnisd]

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

[fastrememberIT]

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 ?

[I_W]

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

[lonenrd]

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.

[developerUtkarsh]

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