(Remade) First Missing Positive | Arrays | Leetcode 41

[@ameyapatil1139]

massive improvement ! well explained.

[@JPN-bx3yd]

Using letters as an example made the solution clear. Great explanation!

[@NideeshTerapalli]

thanks for letting me know David

[@amansahu6799]

Just a small correction, for ind > n, nums[0] = -1*Math.abs(nums[0]), you wrote nums[idn] which will give a arrayindexoutofbounds

[@babbarutkarsh7770]

hey Gfg guy, you are getting better with every video!

[@karankanchetty105]

Great job making it a lot easier to remember. And great improvement.

[@NideeshTerapalli]

Thanks Karan

[@sriram8027]

kzbin.info/www/bejne/npuqo62MqtqCedE

[@ameyapatil1139]

calling out second time - great job !

[@DreamedPlaces]

Very well explained. Thank you!

[@adarshprakashagarwal9427]

Amazing improvement man ...

[@NideeshTerapalli]

Thanks Adarsh

[@BoraElci]

This is so much better!

[@NideeshTerapalli]

Yup!

[@NideeshTerapalli]

0:00 Input/Output 1:45 Brute Force 3:12 Optimized Approach 5:32 Code Explanation 9:50 Example Run Through Feel free to ask me any questions Hey there! Just wanted to let you know that some of the links in this comment are affiliate links, which means that if you make a purchase through them, I may earn a small commission. Don't worry though, it doesn't cost you anything extra and it helps support this channel so I can continue to make more videos for you. Thank you so much for your support, and as always, all opinions are my own! Start getting great at system design: bytebytego.com?fpr=nideesh (affiliate link) Handpicked Algorithms and Data Structures for Interview To Save Time: interviewpen.com/?via=nideesh (affiliate link) Fast track to becoming a knowledgeable SWE www.educative.io/unlimited?aff=K1z6 (affiliate link)

[@Ash-fo4qs]

leetcode 787.

[@arthamsreenivas8858]

Nice explanation Nideesh!

[@jitugosavi]

Very well explained !! You made it so easy to remember.

[@NideeshTerapalli]

Jitendra Gosavi thanks Jitendra

[@utkarshverma5486]

Very nice explanation!

[@chaithnay111]

Nice job and Thank you for the great explanation.

[@NideeshTerapalli]

Youre welcome

[@JannibalForKing]

Well done!

[@NideeshTerapalli]

Thanks Chad

[@maxzhernovkov1602]

I'm not sure, if I am missing anything. It looks like for example for array [-2,1,2,6,4] this algorithm will not produce proper answer?

[@NideeshTerapalli]

The code from the github link I posted in the description will give an output of 3, which is the correct answer when you run in on leetcode

[@maxzhernovkov1602]

@@NideeshTerapalli oh I missed that in the final search you start from "i = 1", not "i = 0" (you didn't emphasize that, so I just thought we start from 0 in the final search).

[@hemantsood9579]

wrong solution explaination of brute force . How your brute force handle the input = [7,8,9,11,12]

[@williamswaney2615]

You add all those to your set, then starting at 1 check if it's in the set. It's not. Return 1.

[@maneeshb1234]

While revisiting array at 9:10 why do need to start loop with i=1?

[@mihirshah426]

not working for [1,2,3,5] expected output : 4 getting : 5

[@NideeshTerapalli]

Can you run it against the code in the description: github.com/Nideesh1/Algo/blob/master/leetcode/L_41.java

[@mihirtrivedi2429]

I don't get it. You saw arr value 2 and invalidated 5 to -5. Now, you lost that information? You won't be able to process 5.

[@NideeshTerapalli]

Hey Mihir can you post the timestamp of the video you are referring to so I know exactly what you're talking about?

[@aishwaryapanicker9817]

@@NideeshTerapalli around 8:05

[@rajanvyas84]

I agree, the last part explanation is not correct, he is negating the position it self, but in the code its suppose to negate the position of the index(which was taken absolute of).

[@RajVerma-qo6bp]

I am not sure that if I am missing anything but for input {1,1,0,-1,-2} I am not getting the correct answer.

[@NideeshTerapalli]

Hi Raj, what answer are you getting? Were you able to figure it out

[@subham-raj]

From when is hashing is brute force?

[@pulse.7]

you’re trying every single combination (just adding all values to the set)

[@ritikchoudhary4206]

Why are we setting numbers larger than array length to be 1?

[@NideeshTerapalli]

We first check to see if 1 is present in the array. If it is, then we know 1 cannot be the first missing positive. So, 1 will be used as an invalidation element. Every number we don't care about is going to be set to 1. We want the first missing positive. If we optimally stuff the array with numbers starting from 1: [1,2,3,4]. The first missing positive will be 5. If we a see number larger than the length of the array, we know it cannot be the first missing positive. Because there must be some smaller number that is missing. That's why we set it to 1

[@ritikchoudhary4206]

Nideesh Terapalli very nice explanation! Thank you man!

[@subhedarsanchay]

I did not understand why did we remove numbers greater than n from consideration?

[@subhedarsanchay]

Oh I see, I did not understand the question correctly. For others who are wondering the same thing, the question is NOT to find first positive missing integer in the range of integers. It's what the question says, first missing positive integer. :facepalm

[@NideeshTerapalli]

Sure Sanchay let me explain. So we define n as the length of the array. Let's say n is 10. We are looking for the first missing positive, so like 1,2,3,4... etc. The array only has 10 spots. So normally, if we are counting from 1 to 10 we could have an array like: [1,2,3,4,5,6,7,8,9,10]. If for example we have a number in the array larger than 10 (n), the array might look like [1,2,3,4,20,6,7,8,25,10]. Here the number 20 and 25 are taking away the places of 5 and 9. That is why we are removing 20 and 25 (greater than n) from consideration. The array can only maximally fit the first n positive numbers. Any number which exists in the array that is larger than n, is taking the spot of some other missing number. Our job is simply to find which is the first missing number. Let me know if you need more clarification

[@subhedarsanchay]

@@NideeshTerapalli Yep, I got it! Thanks for doing this! I appreciate it.

[@pawan2415]

Good explanation. one suggestion please improve your writing :) .