🔴 Amazon Interview Question - Missing Smallest Positive Number | Free Giveaway 🎁

⚠️Rules for 3-month giveaway to Educative website
👉🏻Follow @rachitiitr on Instagram
👉🏻Comment below on this YouTube video, "interested @your_instagram_id_here"
👉🏻A random winner from comment would be decided in 4 weeks
👉🏻The Winner gets contacted on their Instagram with the voucher for giveaway

𝗜𝗡𝗧𝗘𝗥𝗩𝗜𝗘𝗪 𝗣𝗥𝗘𝗣 𝗣𝗥𝗢𝗗𝗨𝗖𝗧𝗦

SUBSCRIBE AND HIT BELL ICON TO CHECK MORE OF MY CONTENT

𝗜𝗠𝗣𝗢𝗥𝗧𝗔𝗡𝗧 𝗣𝗟𝗔𝗬𝗟𝗜𝗦𝗧𝗦

𝗦𝗢𝗖𝗜𝗔𝗟 𝗣𝗥𝗢𝗙𝗜𝗟𝗘𝗦

𝗣𝗥𝗢𝗚𝗥𝗔𝗠𝗠𝗜𝗡𝗚 𝗣𝗥𝗢𝗙𝗜𝗟𝗘𝗦

[sjchat]

the same question they asked me in round 2 of sde 2. I gave an answer of O(N), then suddenly they wanted an answer without extra spaces!! I stucked forever there. 😶

[karthicksridhar]

I guess now i am able to solve leetcode's first missing positive hard question. No resource did this easy explanation. Thanks Rachit.

[abhishekshankar]

This was asked in samsung and VMware interview too

[abhishekvishwakarma]

When I started the video and think of the solution I got the XOR solution but then you threw the O(1) limit then I got stuck😅😅, As always Amazing video Rachit 😎🔥🔥

[rutuja]

This question was really cool. Amazing solution !

[arnavkarforma]

for anyone looking for a bit simpler code, with the same idea

while(i < A.length){
if(A[i] == i+1 || A[i] <= 0 || A[i] > A.length) i++;
else if(A[A[i]-1] != A[i]) swap(A, i, A[i]-1);
else i++;
}
i = 0;
while(i < A.length && A[i] == i+1) i++;
return i+1;

[HarshGangwar]

We can apply the first approach on -ve elements as well by using shifting. shift all -ve values to front and then apply the 1st approach you mentioned for +ve numbers in array.

[EndvrX]

I was asked this as my first question on my Round 1 of Amazon interview and I gave the O(max(element)) soln and he was satisfied. He asked me to optimize it further but was not able to do it. Thanks Rachit for doing such a wonderful solution.

[soumyadeepghosh]

I just changed all negative number to n+1, but thanks to You I got another way to think about the solution. Thanks 😊

[vedkorla]

Dude, the whole animation and production is amazing along with the explanation.

[prasannanivas]

The same code in python runs timeout in interviewbit

[srijansinha]

What if the array is 3 1 3 4 your swapping logic will stuck in loop swapping 3 and 3 repeatedly?

[adipratapsinghaps]

Can such problems even be solved? These are just solutions that you either know, or you don't. How are these interview questions anyway? Crazy.

[ashokbag]

Lmao 😂😂😂, “pause the video! Time to test your brain” and after 1hr of thinking and 4 submissions fails I submitted the correct answer with O(N) TC and the vid stayed paused in that position 😂😂😂

[yogeshwarsharma]

Yes, Its good answer but What about if array has duplicate numbers.

[fireluffy]

What if the elements in given array are not distinct...like there are duplicates. For example the given array is : 1, 3, 3, 6, 7, 8, 9, 9, 10.

[AmanKumar-kzrn]

Guys check out the pepcoding platform on youtube it is the best channel of Data structure and algorithms They also made there content free so grab it

[SaurabhSingh-chnc]

very clear explanation
interested @singhh_saurabh

[manas_singh]

This solution was amazing. I saw a question where the array was sorted and we had to find the mex in log(n) time. I guess we can simply find the point where difference between index and the number is 1 using binary search

[pallavikankure]

Great explanation, but fails for the array with repeated numbers, for ex. [1, 3, 6, 4, 1, -2]. As it swaps with the element at correct position, it enters infinite loop on the 2nd occurrence of 1.