Find the Duplicate Number | LeetCode 287 | C++, Java, Python

LeetCode Solutions: • LeetCode Solutions | L...
June LeetCoding Challenge: • Playlist
May LeetCoding Challenge: • Playlist
Github Link: github.com/KnowledgeCenterYou...
*** Best Books For Data Structures & Algorithms for Interviews:*********
1. Cracking the Coding Interview: amzn.to/2WeO3eO
2. Cracking the Coding Interview Paperback: amzn.to/3aSSe3Q
3. Coding Interview Questions - Narasimha Karumanchi: amzn.to/3cYqjkV
4. Data Structures and Algorithms Made Easy - N. Karumanchi: amzn.to/2U8FrDt
5. Data Structures & Algorithms made Easy in Java - N. Karumanchi: amzn.to/2U0qZgY
6. Introduction to Algorithms - CLR - Cormen, Leiserson, Rivest: amzn.to/2Wdp8rZ
*****************************************************************************
June LeetCoding Challenge | Problem 25 | Find the Duplicate Number | 25 June,
Facebook Coding Interview question,
google coding interview question,
leetcode,
Find the Duplicate Number,
Find the Duplicate Number c++,
Find the Duplicate Number Java,
Find the Duplicate Number python,
Find the Duplicate Number solution,
287. Find the Duplicate Number,
#Facebook #CodingInterview #LeetCode #JuneLeetCodingChallenge #Google #Amazon #DuplicateNumber

[@scarface548]

This is a nice solution despite modifying the array.

[@codestorywithMIK]

Even if you modified the array, this solution is amazing . Thanks a lot for this concept.

[@EduardoSanchez-ym1yf]

Another approach would be to reverse the sign of the elements, as we know that there will be no more than n elements, the repeated element should already have the sign reversed. However, this modifies the array.

[@ijaz2020]

u should modify array

[@Mandeepsingh-jo5cf]

clever solution

[@KnowledgeCenter]

Thanks.

[@kaustubhshirsath4081]

Sir, it is explicitly mentioned in the question that you must consider the given array as a read-only array. But here you are changing the array with each iteration. Could you explain, how can we solve this problem by cycle detection(Floyd's Tortoise and Hare algorithm)?

[@KnowledgeCenter]

You yourself have mentioned the solution.
Check the first number, go to the index 'number', check the new number at this index jump to that index. you will again reach an index if that number is duplicated.
To Find the starting point of Cycle, i.e., the number that is duplicated, Start 2 pointers from beginning.
Advance slow by one step, and fast by 2 step.(Here next means, going to index = value at current index).
Note the index where they meet.
Start 2 slow pointers - 1from meeting point and other from 1st index. They will meet at the duplicate index.

[@lakshyaKumar12]

great and unique approach thank you sir ....

[@KnowledgeCenter]

Thanks.

[@khushalpujara]

Thanks a lot for this amazing solution!

[@maythecodesbewithyou29]

he explains well

[@maythecodesbewithyou29]

Great video brother

[@paragroy5359]

Nice explanation sir..

[@KnowledgeCenter]

Thanks for liking

[@pradeepmondal4943]

Very nice sir 👍..

[@KnowledgeCenter]

Thanks.

[@VidhyashankarMadheswaraswamy]

Nicely explained. Another approach is TotalSum-(n(n+1)/2) = repeated value. n is 4 in this case.

[@srikantsharma6430]

If duplicate value occurs more than 2 times which is a valid scenario then this solution won't work. Test data: [2,2,2,2,2]

[@shubhakardebroy2111]

@@srikantsharma6430 Try this testcase [2,2,2,2,2].

[@YourTechnoByte]

@@srikantsharma6430 I also thought the same solution and was failed in this test case LOL

[@ragavkishoreg]

In Floyd's algorithm , one pointer moves forward by 1 step and other moves by 2 steps . But, here we are jumping from one index to other based on value inside the array . Can you please explain why we are doing it ?

[@KnowledgeCenter]

Here the array values are from 1 to n. And array indices are from 0 to n. So, all the array values are a valid array index.
So, whatever value is there at a given index, go to that index. If a values is repeated, we will go to that index multiple times, i.e., there is Cycle.
So, if we define Next operation as following, we can use Floyd's Cycle Detection to find the starting Node of Cycle i.e., the repeated value.
Next is Defined as:
----------------------
current index = i
current val = nums[i]
Next index = current val = nums[i]
After defining Next it is identical to finding the start of loop in linked list.
Here is the Floyd's Algorithm:
* Check the first number, go to the index 'number', check the new number at this index jump to that index. you will again reach an index if that number is duplicated.
* To Find the starting point of Cycle, i.e., the number that is duplicated, Start 2 pointers from beginning.
* Advance slow by one step, and fast by 2 step.(Here next means, going to index = value at current index).
* Note the index where they meet.
* Start 2 slow pointers - 1from meeting point and other from 1st index. They will meet at the duplicate index.
Once you get this idea, coding Floyd's algo should be trivial.

[@ragavkishoreg]

@@KnowledgeCenter Thank you..

[@SumanPal-wo2xw]

Can't we use map STL and return the number which counts to 2

[@KnowledgeCenter]

It can occur even 3 times, 4 times.. any number of times up to n times.

[@aamodkrishnatiwari127]

Is there no other way to do this? This way seems cumbersome, while being a great solution though.

[@praveenj3112]

We are still modifying original array right ?

[@KnowledgeCenter]

Yes. But, we are at least getting back original array. Avoiding this would require an innovative solution.

[@boloyeung3568]

@@KnowledgeCenter How can you modify a read only array and get it back to original state??? It is clearly stated that the input array is read only (You must not modify the array (assume the array is read only)).

[@KnowledgeCenter]

Looks like another solution is Using Floyd's Cycle Detection Algorithm, though it's less likely that this idea would pop-up during interviews, so I provided an easy solution, which people can arrive at during interviews, that is very close to meeting all conditions and would be accepted by most interviewers.
Here is the Floyd's Algorithm:
* Check the first number, go to the index 'number', check the new number at this index jump to that index. you will again reach an index if that number is duplicated.
* To Find the starting point of Cycle, i.e., the number that is duplicated, Start 2 pointers from beginning.
* Advance slow by one step, and fast by 2 step.(Here next means, going to index = value at current index).
* Note the index where they meet.
* Start 2 slow pointers - 1from meeting point and other from 1st index. They will meet at the duplicate index.
Once you get this idea, coding Floyd's algo should be trivial.

[@aamodkrishnatiwari127]

@@KnowledgeCenter What'd that be?

[@alokcom]

Too complex..