C++ and Java |Brute-Better-OptimalFind the duplicate in an array of N+1 integers | Striver SDE Sheet

[em_nikhil_]

Please never stop this series . You are best and hope to me.😃

[Bishal]

This series is surely gonna blow up and become one of a kind on YT. And the approach Brute-Better-Optimal is amazing. Keep up the good work!

[siddhanth]

I can't stress how much I appreciate this! Knowledge should not be a resource hoarded only by a select few and the fact that you're sharing all this content for free reinforces my belief that today, there is never going to be a need to pay for knowledge, thanks to people such as yourself. Thanks again man, great work!

[ankur.singhs]

If you are going to solve all your questions of that sheet, then a big thanks to you brother.

[soumavabanerjee]

Even after your full time work, you're providing this much help! Massive respect for you!

[takeUforward]

Leave a comment, mentioning about the feedback, be it good or bad, but please do leave :), xor method will not work.. {2, 2, 2, 2}, take this example! Negation of index does not work because it modifies the array.
.
Oops, sorry, I uploaded 720p instead of 1080p :| The next set of videos go slow and are in 1080p as this was a feedback video, so kindly don't judge on this video.

[Nikhilsharma-dptw]

Intiution & proof:
1. First collision: (when fast meets slow in the cycle) (This will help to find whether cycle exists or not.)
fast is just moving twice the speed as slow. slow is moving 1 unit, fast is moving at 2 units. so, fast = 2* slow. now take some distance n(consider it as a ring road :-p )
To cover distance n, slow needs n units
fast needs 2n units right (fast =2*slow)
This mean eventually they are meeting. I hope this makes sense.
2. Finding where collision occured (the entry point/duplicate number in this case):
From (1)-> we already know there is some entry point (where cycle starts) & a meeting point (where fast meets slow).
lets say distance from starting point to entrypoint = d1;
distance from entrypoint to meetingpoint = d2;
distance from meetingpoint to entrypoint (which makes cycle) = d3;
slow covers d1 distance and d2 to reach meeting point, so slow = d1+d2;
fast covers d1, d2 d3 and again d2 to reach meeting point, so fast = d1+d2+d2+d3 = d1+2d2+d3
from 1, we know fast = 2* slow
d1+2d2+d3 = 2(d1+d2) which mean ( d1=d3 )
It concludes distance between d1 (starting & entry) equals d3(meetingpoint to entrypoint), thats the intuition behind starting fast pointer at head for the second time and moving both 1 unit, at equal distance theyll find the duplicate/entrypoint.

[written_syntax]

Another method ::
int main()
{
int n;
cin>>n;
vector<int>v(n);
for(int i=0;i<n;i++)
{
cin>>v[i];
}
int sum=accumulate(v.begin(), v.end(), 0);
int rep=sum-(n-1)*n/2;
cout<<rep<<"\n";
return 0;

}

[em_nikhil_]

Wow i never thought that i can use hare and tortoise method in arrays. I only used it in linked list.

[koushik]

It's been a year since you started this series! Congratulations!!!

[himanshidixit]

I was searching for copper on YT and found real gold here..Hats off sir..Amazing series..

[yashparmar]

I have one more approach which is also O(n) in time complexity and O(1) in space complexity.
As many of us might find difficulty while solving question using linked list therefore what I am doing is that just traverse through an array and then whatever that value of the element is suppose a[0] = 4, then we just reverse the sign of 3rd element in the array (assuming 0 based indexing) and we do that for whole . Once we completed traversing we only left only 1 positive element therefore our ans is index of that element + 1 ( because it's 0 based index).
Let's understand this by an easy example suppose we have given an array a = [1, 3, 2, 2] and it's also given that all the elements in an array is in the range 1 to n(inclusive) there we start traversing through an array.
Initially a[0] = 1 therefore we invert the sign of 0th element(1-1) now our array becomes -1, 3, 2, 2 after that we move forward now we have a[I] = 3 therefore we invert the sign of a[2] which implies now our array is -1, 3, -2, 2 then we do that with rest of the elemts and one thing that you need to keep in mind is always take absolute value of the element because we are inverting therefore at last we have -1, 3, -2, 2 now the first positive value is 3 with index 1 implies our is 2.
You might be thinking of that 2 is also positive but why it's not the answer it's because the index of 2 is 3 but n is 3 therefore it is not possible.

[VibhorMittal]

A suggestion/feedback, since you've told in your previous videos that interview problems are usually not same as leetcode problems but mostly are variations of it.
Could you please suggest some ways we can think about these variations, let's say in this case duplicate number problem.
Thanks a lot. 👍🙏

[siddharthapalav]

Bro your explanation is awesome 👌🏼, just that as the audio was a little late when you were taking example of “slow and fast pointer” I lost the track. It would be great if audio and video are in sync.

[amanaswal]

Amazing tutorial. I love the way you told us the brute force then the optimized solution. I used to solve this question using hash, but got to know a better approach today. Thanks 👍

[kumarsaurabhraj]

Intuition / Logic
The repeated number will always be at the junction between the straight path and the cycle because, the cycle exists only because two nodes reach to the same next as one value is repeated. We traverse the array and we go to the element at the index same as the current element value. Since there is a repeated value, we would be going to a index twice, hence there will be cycle if there is a repeated value. This method is only applicable to questions in which all elements are between 0 and array.length - 1 . Two pointer in a cycle, starting at the same point and moving at different speeds will always collide at some point. At any point when the slow and fast pointers collide the fast pointer must have covered twice the distance of the slow pointer because its moving two steps in every iteration while slow pointer moves only one. And where would the fast point move that extra distance? It could only move that in the cycle because that is only how it could come back the same point in the cycle, as the slow and fast are colliding at a point in the cycle, hence the distance moved by the slow pointer would be multiple of the length of the cycle. At last we would move both the slow and fast pointer by one step until they meet again and that would be our duplicate number.

[HarshitSingh-itkp]

Thanks a lot, striver you have been a great mentor to us all tier 3 aspiring engineers. Keep up the good work.

[aryanbhandari]

In Java : Suppose example array ={2, 3, 5, 2, 7, 22}
If you try array[22], it would give index out bound exception . And thats happening with this test case and the most optimized Code you provided .

[ankur.singhs]

Can you make a video on Time Complexity because I and my friends struggle a lot. First we are not able to exactly calculate our codes complexity (we just guess it) and after that we are not able to think a solution having better complexity.

Please can you make one ? It will help a lot of students like me.

[aayush]

before this i watched neetcode video . he made last approach very complex but you explained very easily . thanks .