Amazon Coding Interview Question - First Missing Positive (LeetCode)

Here is a step by step explanation of a hard array problem asked at Amazon!
Check out my interview prep platform for learning the patterns!
📢 Interview Prep Platform: algoswithmicha...
🎧 Join the community Discord: / discord
💰 Support me on Patreon: / michaelmuinos
🔗Follow me on LinkedIn: / michael-muinos
📂Follow me on Github: github.com/Mic...
In this video, I go over the problem "First Missing Positive". This is a hard problem asked at many tech companies including Amazon, Bloomberg, Google, and many more. This problem would be considered an easy/medium if there wasn't a restriction that we must have a solution with constant extra space.
In the brute force approach, we could add all of the numbers we have in our input to a set. Then, we perform a loop from 1 to N where N is the number of elements we have in our input and check if the number is present in the set. If the number we are on is not in the set, we found our first missing positive. The brute force approach involved a linear time AND space complexity.
Now, in the optimized approach, it takes 3 steps to solve this problem. For step 1, we must convert any negative numbers and numbers greater than N to a 1. This is done to restrict our range of numbers. For step 2, we use the range of numbers as indexes to our array and perform a lookup to swap the sign of the element at the index. This will signify we have seen the positive number without doing any sorting. In the final step, we look for the first non-negative number, if we find one, the index + 1 is the first missing positive; however, if we don't find it, we know the answer will be N + 1.

[@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!

[@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.

[@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!

[@vinodrammohan]

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

[@AlgosWithMichael]

Glad it was helpful!

[@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.

[@faridaragab_]

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

[@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!

[@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.

[@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!

[@hamsalekhavenkatesh3440]

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

[@javaguru7453]

kzbin.info check this too

[@AlgosWithMichael]

Thank you!

[@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!

[@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

[@vibhoragarwal5425]

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

[@AlgosWithMichael]

Thanks, will do!

[@AM-nv4ol]

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

[@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!

[@avdeshpatel8631]

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

[@AlgosWithMichael]

Thank you!

[@gauravbhattacharjee4379]

Michael, I found gold again! This one

[@javaguru7453]

kzbin.info check this too

[@louistannudin2486]

This solution was better than the leetcode solution article

[@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

[@laugh_d_tale]

that was the simplest solution i watched . Thank you!

[@AlgosWithMichael]

Glad it helped!

[@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!

[@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

[@vincenttan6303]

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

[@AlgosWithMichael]

Thanks, that was my goal!

[@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.

[@dmsohel1335]

this was the best solution i have ever seen

[@AlgosWithMichael]

Thank you so much!

[@sanjayizardar2263]

Great solution.. please keep posting hard problems like this

[@AlgosWithMichael]

Glad you liked it! Thanks for watching.

[@vishalpapnai5461]

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

[@AlgosWithMichael]

Glad I could help :)

[@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!

[@aviralpandey4096]

You made it look so easy. Thanks a lot.

[@AlgosWithMichael]

Glad it helped!

[@陈瀚龙]

Great problem, and great explanation. Thanks!

[@AlgosWithMichael]

Thank you very much!

[@gurpartapsingh1693]

Beautifully explained.. keep it up brother

[@AlgosWithMichael]

Thank you man!

[@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!!

[@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!

[@indrianids]

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

[@UtkarshShrivastava6009]

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

[@AlgosWithMichael]

Awesome, glad to hear!

[@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

[@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!

[@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!

[@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 👌

[@bekjanomirzak224]

Thank you this great explanation.!!!!!

[@AlgosWithMichael]

Thanks

[@parmanirahulpawan27]

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

[@AlgosWithMichael]

You're very welcome!

[@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?

[@Er0Shara]

awesome explanation, keep going!

[@AlgosWithMichael]

Thanks, will do!

[@connect2krish]

Great explanation! Very helpful. Thanks!

[@AlgosWithMichael]

Thank you!

[@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

[@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!

[@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!

[@javeedbasha6088]

Great explanation. Please do more leetcode hard problems.

[@AlgosWithMichael]

Thank you!

[@warnercooler4488]

So well explained! Thank you so much!

[@AlgosWithMichael]

Glad you enjoyed it!

[@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

[@psn999100]

That was an amazing explanation. Thanks

[@AlgosWithMichael]

No problem, thank you for watching!

[@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?

[@VishalSharma-hq5ti]

Amazing explanation bro.. keep it up!!

[@AlgosWithMichael]

I appreciate it, thank you!

[@code7434]

Super awesome ,very tricky problem

[@AlgosWithMichael]

Yea it definitely is!

[@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

[@sergten]

Nice trick. Probably applicable to other problems.

[@AlgosWithMichael]

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

[@lokeshkumarrathinavel6566]

good explanation. you opened my eye. thanks Man.

[@AlgosWithMichael]

Glad to hear it!

[@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)

[@geodude9395]

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

[@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.

[@deepanshuchawala216]

Bro, Thanks a lot . You saved us.

[@AlgosWithMichael]

Haha awesome, glad it helped!

[@nikhilbhujbal8927]

Great Explanation bro .

[@AlgosWithMichael]

Thank you 🙂

[@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?

[@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)

[@theuser7288]

Explained very well.

[@AlgosWithMichael]

Thank you!

[@arpit_singh10]

Great explanation bro

[@AlgosWithMichael]

Thanks man!

[@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

[@madhuravp]

Amazing explanation!

[@AlgosWithMichael]

Thanks!

[@javaguru7453]

kzbin.info check this too

[@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.

[@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

[@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

[@prasanthkumar6393]

Good solution ❤

[@jitendrasinghbisht2289]

This is awesome. Thanks Man

[@javaguru7453]

kzbin.info check this too

[@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

[@a-33-akshaymishra5]

very well explained!

[@AlgosWithMichael]

Glad to hear, thank you!

[@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!

[@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!

[@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!

[@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...

[@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!

[@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]

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!

[@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.

[@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

[@Tarun_Kumar_bhu]

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

[@HARSHITKUMAR-wj4ex]

very helpful. Thanks!!

[@AlgosWithMichael]

You're welcome! Thanks so much for watching!

[@oxanasf6369]

So far it's the most clear explanation even though I work with python. ps Still would be great to have it on python.

[@AlgosWithMichael]

Glad it helped!

[@tirthjayswal9895]

Awsome Dude ..best

[@AlgosWithMichael]

No problem man!

[@rak590]

Please post more videos :)

[@AlgosWithMichael]

More every week!

[@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*

[@interviewprep6827]

can you post a link to the code please??

[@codestorywithMIK]

Amazing

[@AlgosWithMichael]

Thanks!

[@mrinalmathur8185]

Why are we doing index+1 to search for the number value of index? in 11:29

[@AlgosWithMichael]

Because index is 0 based, thus we must offset it. Thank you for watching!