Amazon Coding Interview Question - First Missing Positive (LeetCode)

[@keithnorm82]

What a ridiculous problem lol. Can pretty much say I would have never thought of doing it this way. Thanks for the explanation!

[@AlgosWithMichael]

lol yea, the optimized solution is definitely an "outside of the box" approach. Thanks for watching!

[@manishpundir9625]

When u started with Brute Force it helped everyone to understand the concept. I have no words how to say thank you. Great work indeed. You earned one more subscriber.

[@AlgosWithMichael]

Wow awesome glad to hear!

[@pruthvirajk6019]

You are awesome ...Basically we are making the numbers inside the array to be in between 1 and n and traversing the array again to mark each and every elements presence by changing the sign at that index which indicates that we have seen the element,Now since we need the smallest number in between 1 and n we are traversing the array again from start....You are really Awesome

[@AlgosWithMichael]

I appreciate it man! It's a challenging problem for sure haha, thanks for watching!

[@PATRICKCHUAD]

thanks for hints that we are only be looking from 1-8. I have seen other video but only now I understand this concept. your explanation is very clear.

[@JakeyCroth]

Awesome awesome solution. Thank you for it! So refreshing to see it drawn out and explained in full, as opposed to the scores of videos out there that fail to do that.

[@AlgosWithMichael]

Thanks man! I'm a visual learner myself so a whiteboard explanation makes the most sense haha

[@Sumit-yn7dn]

@@AlgosWithMichael bro but if we don't have 1 in array then this code fails as you are swapping every negative number with 1 then this will be marked visited ????

[@anurandutta2217]

@@Sumit-yn7dn that's why he is using a variable to check if 1 is present or not during the first traversal.

[@faridaragab_]

The Tone of your voice makes me wanna continue listening forever .. so clear .. Thanks for the awesome video .. ✨

[@vinodrammohan]

The best explanation ever. Thank you so much for explaining slowly with diagrams for each edge case

[@AlgosWithMichael]

Glad it was helpful!

[@HungNguyen-tp6vt]

thank you. From start I didn't understand but after watching your video many times. I do understand what you said. It's awesome solution.

[@hamsalekhavenkatesh3440]

brilliant solution. I love the way how this problem reduced to cyclic sort

[@javaguru7453]

kzbin.info check this too

[@AlgosWithMichael]

Thank you!

[@leo8292]

Great solution. I kept attempting to define some flags to create a sort of bound in which I could find the number between the upper and lower values, but this is way more straight forward and elegant. I wonder how you get to a solution like that on your own. Thanks for posting!

[@AlgosWithMichael]

Some of the solutions, at least to me, seem too difficult to come up with on your own. In an actual interview you would be getting hints and what not. Thanks for watching!

[@louistannudin2486]

This solution was better than the leetcode solution article

[@amandapanda3750]

This is such a silly problem, Wouldn't have thought of this solution. Thanks a lot for your explanation.

[@AlgosWithMichael]

lol yea it is a ridiculous question

[@SwapnilSarkar]

Hi man! I don't know if you still read the comments of this video but still want to say that your explanation was great. I am sure that I won't ever forget the approach of this solution. Thank you!

[@AlgosWithMichael]

Glad I could help!

[@prajaktakarandikar3459]

Hope you are better now. Thanks for the video. Great explanation.

[@AlgosWithMichael]

All better now! Thanks for watching!

[@ganeshchowdhary3024]

Awesome idea handling negative numbers. This should be present in the leetcode solution.

[@AlgosWithMichael]

Agreed, thanks for watching!

[@avdeshpatel8631]

after seeing the video problem looks easy, great explanation on whiteboard !!

[@AlgosWithMichael]

Thank you!

[@vincenttan6303]

this is better than the provided solution in LC which I couldn't understand.

[@AlgosWithMichael]

Thanks, that was my goal!

[@bbbo85]

that's so clever but shouldn't negatives and elem > n just be some number greater than n? for example 8 because if there weren't any 1s, you would've marked 1 as seen

[@gauravbhattacharjee4379]

Michael, I found gold again! This one

[@javaguru7453]

kzbin.info check this too

[@vibhoragarwal5425]

Just awesome extremely clear explanation not less than any professional keep making videos it helps us lot thanks man

[@AlgosWithMichael]

Thanks, will do!

[@capoditutticapos19]

Very clear explanation man. This question is crazy though. Ns how a person would get the 'a-ha moment' to think of these steps, especially under pressure of an interview. Maybe i can't step inside the head of a genius lol.

[@UtkarshShrivastava6009]

After watching the first 10 mins, this problem became an easy one.

[@AlgosWithMichael]

Awesome, glad to hear!

[@AM-nv4ol]

you're a godsend man. amazing explanation throughout. thank you.

[@dmsohel1335]

this was the best solution i have ever seen

[@AlgosWithMichael]

Thank you so much!

[@yitingg7942]

How can you explain it so well each time Michael? I am so amazed and really appreciate you!! One follow up, I also did 268. Missing Number and tried to use the same logic here, but how come I just couldn't get it right? Why is that the logic applies here but doesn't apply to an easy problem ?

[@AlgosWithMichael]

Thank you so much! I believe the problems are different in the sense of what values are allowed inside of the arrays.

[@yitingg7942]

@@AlgosWithMichael Yes you are absolutely right! Thank you for your reply!!

[@indrianids]

Thanks, it's awesome solution!! have think about this case about 2 days haha

[@aviralpandey4096]

You made it look so easy. Thanks a lot.

[@AlgosWithMichael]

Glad it helped!

[@laugh_d_tale]

that was the simplest solution i watched . Thank you!

[@AlgosWithMichael]

Glad it helped!

[@aaryanbudhirajamusic6874]

Thank you so much! Amazing Explanation! Subscribed man! Initially, I thought it was an easy problem lol but then I saw your video and saw it was a Hard one, felt less guilty !

[@AlgosWithMichael]

Haha yea its a tough problem to get down to constant space. Thanks for watching, commenting, and subscribing!

[@sergten]

Nice trick. Probably applicable to other problems.

[@AlgosWithMichael]

Yep, this trick is definitely seen in a lot of array restricted problems.

[@fatimamaj7964]

Thanks for your great explanation. I am just not sure why when I try the same way for solving the problem with 'python' I got this result from LeetCode: Runtime: 1314 ms, faster than 10.62% of Python online submissions for First Missing Positive. Memory Usage: 52.1 MB, less than 57.17% of Python online submissions for First Missing Positive. which there is high difference with your result

[@CronusVelox]

JAVA is faster than Python. Also, internet speed can skew your runtime I'm leetcode. I wouldn't worry about it 👌

[@raveenadsouza2095]

Quick question, for the brute force, why do we add it to a set and then check? Could we not just check if if i (from 0 -> n) is in the list provided? Is it because finding it in a set rather than a list is O(1) rather than O(n)?

[@AlgosWithMichael]

The list is not sorted, so I don't think we can check if i (from 0 -> n) is in the list on its own.

[@raveenadsouza2095]

@@AlgosWithMichael Oh I meant specifically for python there’s the “in” keyword to find a value in a list so doing for i in range(1, len(nums)+1): if i not in nums: return i

[@heisenberg1844]

About changing out-of-range numbers to 1, what if 1 is not present in the original array? In that case you'd be adding the number 1 to the array, and hence you won't get 1 as the first missing positive number.

[@AlgosWithMichael]

I do a check if 1 is not present before getting to the main part of the algorithm. So, `if (containsOne == 0) return 1`

[@heisenberg1844]

@@AlgosWithMichael Loud and clear. Thanks.

[@AlgosWithMichael]

Nice, glad it helped!

[@ashishdukare1313]

Thank you so much for such an easy explanation. This just saved my day :). Keep making more such videos.

[@AlgosWithMichael]

Anytime! More videos coming every week!

[@rohanasokan7338]

Damn! Saved your day? What really happened to your day? xD

[@dips2113]

This was super helpful and was explained very well. Thank you!

[@AlgosWithMichael]

I'm so glad you found it helpful, more videos to come!

[@biswamohandwari6460]

Man your explanation is brilliant. Awesome!!! Thanks, dude.

[@AlgosWithMichael]

Glad it helped!

[@vishalpapnai5461]

great explanation Michael. you saved me a lot of time.

[@AlgosWithMichael]

Glad I could help :)

[@gurpartapsingh1693]

Beautifully explained.. keep it up brother

[@AlgosWithMichael]

Thank you man!

[@javeedbasha6088]

Great explanation. Please do more leetcode hard problems.

[@AlgosWithMichael]

Thank you!

[@bekjanomirzak224]

Thank you this great explanation.!!!!!

[@AlgosWithMichael]

Thanks

[@saulgoodman6710]

can you tell us how does one need to think of the optimized solution? by practice? or any helpful resources that we need to study for these kind of stuff?

[@Haibrayn42]

Why not swapping the numbers to their correct indices instead of looping and modifying the out of bounds to 1? That way in the first loop you would the array in the correct order. In a second loop you can just start with missing=1 and increment it every time you find a number in the correct position, and just break if found a number in the wrong position and return the missing var

[@paras203]

Thanks Michael for the explanation. Just one doubt, if we are making everything greater than or all negative numbers to 1. Now if array is 2,3,8 it gets converted to 2,3,1 and then we check indexing and it will fail and answer will be coming as 4 but it should be 1. Please correct me if i understood it wrong.

[@AlgosWithMichael]

There is a check if there is a 1 in the array before we start changing the values. So if we do NOT find a 1, then we know our answer is 1. It is an edge that we have to consider. 16:11 is where the edge case is handled. Thank you for commenting and watching, I appreciate it!

[@paras203]

@@AlgosWithMichael Got it Michael. Around 13 minutes,, coding started. So paused the video and was analysing the algorithm and found it. Anyways, Keep up the good work. Thanks. :)

[@AlgosWithMichael]

Anytime!

[@KanagaveluSugumar]

will it work with [2, 3, 4] where 4 will be swapped to 1 then [2, 3, 1] and all are negative, and the result 1 will not be found? instead 4 will be found? The problem is; it is not sure 1 as an existing value or added as replacement for edge case (negative or greater than size of array)

[@陈瀚龙]

Great problem, and great explanation. Thanks!

[@AlgosWithMichael]

Thank you very much!

[@JoffreyB]

so what if we get numbers like [7, 8, 9], then we replace whatever is greater than n or less than 1 is 1, we get [1, 1, 1], than we use "seen" step, we get [-1, 1, 1], solution would be first non-negative number's index + 1, i. e. = 2, which is not true, should be 1. What gives? Where did I get it wrong?

[@talwaar007]

There is no way somebody would work this out in a one hour interview. I figured out a slightly sub-optimal solution which relied on first sorting the input array in about an hour but there is no way in hell I would have figured this out (in fact I couldn't figure it out regardless of time limit).

[@code7434]

Super awesome ,very tricky problem

[@AlgosWithMichael]

Yea it definitely is!

[@warnercooler4488]

So well explained! Thank you so much!

[@AlgosWithMichael]

Glad you enjoyed it!

[@lokeshkumarrathinavel6566]

good explanation. you opened my eye. thanks Man.

[@AlgosWithMichael]

Glad to hear it!

[@AbhishekChauhan-df3vb]

oh wow! I was thinking of so many other ways! shit, I knew this topic of absolute(). Really great explanation, thought me to think how to use techniques that I already know :) thanks a lot man! great video

[@AlgosWithMichael]

Yea, it very tricky haha, thanks for watching!

[@sanjayizardar2263]

Great solution.. please keep posting hard problems like this

[@AlgosWithMichael]

Glad you liked it! Thanks for watching.

[@geodude9395]

God Bless You. Because Jesus Christ, Finally someone explains it in English.

[@3dhakim]

This is very helpful! can you help on this Michael Muinos Write a function: int solution(int A[], int N); that, given an array A of N integers, returns the smallest positive integer (greater than 0) that does not occur in A. For example, given A = [1, 3, 6, 4, 1, 2], the function should return 5. Given A = [1, 2, 3], the function should return 4. Given A = [−1, −3], the function should return 1. Write an efficient algorithm for the following assumptions: N is an integer within the range [1..100,000]; each element of array A is an integer within the range [−1,000,000..1,000,000].

[@AlgosWithMichael]

if it is a problem on leetcode, post the problem and ill add it to my list

[@luciferrex9613]

Hi thanks your videos are very nicely explained you got a lifetime subscriber for you .. please keep the good work

[@AlgosWithMichael]

Thank you so much, that means alot!

[@anurandutta2217]

Great explanation! Immediately subscribed after watching this video. Btw are you a student or a working professional?

[@AlgosWithMichael]

I appreciate that! I currently work full-time as a Software Engineer.

[@anurandutta2217]

@@AlgosWithMichael Your videos are very helpful! Keep up the good work 👍 May I know which company are you currently working for?

[@AlgosWithMichael]

I work for a mid-sized company in LA, not a FANG or anything like that!

[@parmanirahulpawan27]

Thank you so much. You explained it so well. Super helpful!

[@AlgosWithMichael]

You're very welcome!

[@theuser7288]

Explained very well.

[@AlgosWithMichael]

Thank you!

[@connect2krish]

Great explanation! Very helpful. Thanks!

[@AlgosWithMichael]

Thank you!

[@Er0Shara]

awesome explanation, keep going!

[@AlgosWithMichael]

Thanks, will do!

[@ShashwataSaha]

from heapq import heapify, heappop class Solution: def firstMissingPositive(self, nums: List[int]) -> int: nums=set(nums) nums=list(nums) heapify(nums) cnt=0 while len(nums)>0: temp=heappop(nums) if temp

[@AlgosWithMichael]

Yea, it is a good solution, but I would imagine in an interview they would want the more optimized approach

[@psn999100]

That was an amazing explanation. Thanks

[@AlgosWithMichael]

No problem, thank you for watching!

[@starc701]

I dont understood why we cannot write step to else if condition with (Nums[i] n) shouldn't we eleminate zero also. Since we want range 1 to n.. Why then we are only excluding negative and greater than n. You did corrected that at end... I saw it.. Updated comment.

[@AlgosWithMichael]

Haha yeah I messed up

[@starc701]

@@AlgosWithMichael it was very helpful bro... Keep up the excellent work.

[@aishwaryavenkat3029]

Similar to counting sort where we use cur value as index and modify value in that index. Is there a generic name for that technique ? How do one comes up with such technique?

[@javaguru7453]

kzbin.info check this too

[@nikhilbhujbal8927]

Great Explanation bro .

[@AlgosWithMichael]

Thank you 🙂

[@deepanshuchawala216]

Bro, Thanks a lot . You saved us.

[@AlgosWithMichael]

Haha awesome, glad it helped!

[@alammahtab08]

👍👍 I had to go over this twice to make it stick in my head. Below is the commented code, in case anyone wants to try out. class Solution { public int firstMissingPositive(int[] nums) { if(nums == null || nums.length == 0) return 1; int n = nums.length; boolean containsOne = false; // Step 1 : Sets the containsOne flag to true if input array contains 1 , // also sets all the negative numbers, zero and number's greater than n, to 1 // Make sure you don't mess up the order of statements for(int i = 0; i < n; i++) { if(nums[i] == 1) containsOne = true; else if(nums[i] n) nums[i] = 1; } // if array doesn't contains 1, the first missing positive will be 1 if(!containsOne) return 1; // Step 2 : This step marks the number we have seen, by setting its index // position to a negative number // e.g. if nums[i] = 7, since 7 should come at index 6 (that's why - 1, array indexes starts with 0) // we mark nums[6] = nums[6] * -1 (if nums[6] was not already negative) for(int i = 0; i < n; i++) { int index = Math.abs(nums[i]) - 1; // if its already negative, we don't do anything if(nums[index] > 0) nums[index] *= -1; } // Step 3 : Finally, look for a non negative number in the array // If we find an index i, such that nums[i] is positive, that means // we didn't see the number which should come at this index i // the number that should come at index i should be i+1, so we return i+1 for(int i = 0; i < n; i++) { if(nums[i] > 0) return i + 1; } // If we reach here it means, original input array had all the positive numbers // from 1 to n, so the first missing positive number will be n + 1 return n + 1; } } Tip (Catch bugs in implementation) : Run your code through some examples : [1, 2, 3], [1, 2, 2], [1, 3, 3], [2, 2, 2], [4, 5, 1] github.com/eMahtab/first-missing-positive

[@AlgosWithMichael]

Yea, its a very complicated solution, definitely not intuitive haha

[@0anant0]

thanks for the helpful comments in your code -- the step 3 comments helped me understand why we are doing this!

[@carliux8888888]

I would never find this solution during an interview... Best I could do is O(N) time and space complexity by using a hash table...

[@bhavyabansal1143]

if all numbers are negative lets say -1,-2,-3, then first missing positive is 1 not array.length + 1.. how come this solution works then?

[@rak590]

Please post more videos :)

[@AlgosWithMichael]

More every week!

[@amu281]

Hi MIchael, I have a doubt if you could clear. How it will behave for [-5, -4, -3] .

[@AlgosWithMichael]

I believe 1 would be the returned answer

[@codingepocs2410]

best explanation thank you

[@javaguru7453]

kzbin.info check this too

[@dhavalkolapkar1772]

Awesome explanation. I have a question, why use a set? cant we just do Array.contains() ?

[@cbjueueiwyru7472]

Set is o(1) lookup. Array.contains is o(n)

[@madhuravp]

Amazing explanation!

[@AlgosWithMichael]

Thanks!

[@javaguru7453]

kzbin.info check this too

[@prasanthkumar6393]

Good solution ❤

[@mohdaman7958]

Hi thanks. But you explained this in a very complex way. We are all three friends unable to understand. Could you please make it a little bit simple.

[@jitendrasinghbisht2289]

This is awesome. Thanks Man

[@javaguru7453]

kzbin.info check this too

[@cbjueueiwyru7472]

What if 1 was the missing positive number. Wouldn't switch those to 1 mask that?

[@AlgosWithMichael]

I do a check if the missing number is 1, it is an extra edge that is definitely a gotcha!

[@VishalSharma-hq5ti]

Amazing explanation bro.. keep it up!!

[@AlgosWithMichael]

I appreciate it, thank you!

[@a-33-akshaymishra5]

very well explained!

[@AlgosWithMichael]

Glad to hear, thank you!

[@ArghyaBhattacharyaNITA]

Just a suggestion, avoid turning the non-relevant numbers to 1, because what if the missing number is 1. I would just change them to a string. And while iterating the list, ignore the number if its type is string.

[@AlgosWithMichael]

You can just have an edge case of checking for 1 before flipping

[@nidhimittal9521]

Thanks for the amazing explanation! I have one question if(nums[i] == 1) containsOne = true; else if(nums[i] n){ nums[i] = 1; Why the second condition is inside else if? If we have 1 in an array does it mean we don't want to update number less than equal to 0 and greater than n to 1?

[@khateebanwer7466]

He combined the first step and the initial step to deal with an edge case:- 1) we set all values =1 that aren't needed to proceed to the second step. 2) We also use a flag variable to see if it encounters 1 in the array in the first pass itself and if it doesn't enocunter a 1 in first pass i.e that smallest missing positive value would be equal to 1 3) after first pass / first execution phase , we would've checked for both the edge case (i.e 1 exists in the array or not) and also converted the useless values to one to start the next phase thereby skipping one more loop that would run till nums.length for this phase if this edge case was dealt seperately.

[@code7434]

we can replace out of bound numbers by INT_MAX? then during second iteration if abs(nums[i]) is INT_MAX just continue?

[@VishalSharma-hq5ti]

Agreed I think replacing by 1 might cause an error? I think we can replace out of range numbers by any number in the range(1...n+1), provided that number is present in array or else we can choose an arbitrary number(e.g. INT_MAX)

[@AlgosWithMichael]

Yea I believe you could. However, I could see an edge case where a number in your array is INT_MAX. Thanks for watching!

[@veliea5160]

Can you please solve leetcode 84- Largest Rectangle in Histogram. It is a hard problem and there is not good explanation on youtube

[@AlgosWithMichael]

Yea sure 👍

[@veliea5160]

@@AlgosWithMichael thank you

[@arpit_singh10]

Great explanation bro

[@AlgosWithMichael]

Thanks man!

[@tirthjayswal9895]

Awsome Dude ..best

[@AlgosWithMichael]

No problem man!

[@sudiptahalder423]

I think inside first for loop part, in the else if condition it should be (nums[i]n) instead of (nums[i]n). Just run it for the testcase [1,2,0]. You will get it. The index will be be (-1) when encountering nums[3]=0. But there is no index (-1) in the vector. The following code of mine got accepted: class Solution { public: int firstMissingPositive(vector& nums) { int n = nums.size(); int i; if(n==0) { return 1; } else { bool contains_one=false; for(i=0; i

[@AlgosWithMichael]

Yea, I fix that later on in the video haha. Thank you for commenting and watching!

[@sudiptahalder423]

@@AlgosWithMichael yea very nice explanation

[@AlgosWithMichael]

Thanks so much!

[@Nickel80]

Thanks for the great explanation. Is there a name for this technique?

[@AlgosWithMichael]

Not really. The solution to this problem is really unique haha. Thanks for watching!

[@javaguru7453]

kzbin.info check this too

[@nitensapkota8606]

Use cyclic sort ignore negative numbers

[@ShashwataSaha]

How am I sure there will be always 1 in my test case?

[@AlgosWithMichael]

There won't necessarily always be a 1 in your test case, but it is an edge case you must handle if there is

[@anshuldogra7607]

What if the array is like A[] = {28,10,18,99,70} ?? In this case your logic that the missing number will lie between 1 to n+1 doesn't hold ! Am I missing something here ??

[@AlgosWithMichael]

The first missing positive in the example you provided is 1. You know your missing number will always be in the range of however many elements you have. The +1 comes from an example such as this [1, 2, 3], the first missing number would be n + 1 where n = 3, 3 + 1 = 4.

[@anshuldogra7607]

@@AlgosWithMichael I had understood the problem incorrectly. I thought it has to be the next missing positive which in this case would have been 11. Thanks for the explanation. You've got yourself a new subscriber :)

[@AlgosWithMichael]

Thanks so much!

[@HARSHITKUMAR-wj4ex]

very helpful. Thanks!!

[@AlgosWithMichael]

You're welcome! Thanks so much for watching!

[@SC2BuildOrder]

Why do you check the absolute value in step 2? You already turn all negatives into positive 1s in step 1...?

[@SC2BuildOrder]

nvm, im dum

[@AlgosWithMichael]

Haha naw it's a confusing solution

[@tejasghone5118]

That was smart ; ) . Thank you!

[@AlgosWithMichael]

No problem!

[@AmitSharma-wx1wj]

what happens for [0,1,2] -> 0 -1 = -1 wil come right?

[@AlgosWithMichael]

We do an absolute value check of the index so no index out of bounds. Also, the 0 will get changed to a 1 before the negation step!

[@AmitSharma-wx1wj]

@@AlgosWithMichael For 0, it is not set it to 1 -- in first loop. So in second loop, int index = abs(0) - 1 = -1 will give out of bounds man.. let me know if I m missing something

[@AlgosWithMichael]

If you go to 19:27, I fix that mistake of not doing `

[@AmitSharma-wx1wj]

I was trying to do it of my own after watching your approach which confused me.. you are right ! Thanks for the video !

[@AlgosWithMichael]

Gotcha, well thank you commenting and watching!

[@kose241]

Lol I first thought it was the first missing number in the in between the smallest and largest number in the array

[@AlgosWithMichael]

The LeetCode descriptions can be annoying af

[@kose241]

@@AlgosWithMichael definitely

[@Tarun_Kumar_bhu]

[2, 2, 2, 2, 2] is it going to work?

[@shaileshhegde9205]

That was awesome!

[@AlgosWithMichael]

Glad you liked it!

[@javaguru7453]

kzbin.info check this too

[@sandeepkumawat4982]

best explanation ...

[@AlgosWithMichael]

I appreciate that, thank you

[@psychoticgamer6853]

Why I'm hearing *Intelligence beat*