First Missing Positive - Leetcode 41 - Python

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
Coding Solutions: • Coding Interview Solut...
Dynamic Programming Playlist: • House Robber - Leetco...
Tree Playlist: • Invert Binary Tree - D...
Linked List Playlist: • Reverse Linked List - ...
Problem Link: leetcode.com/problems/first-m...
0:00 - Read the problem
1:35 - Drawing Explanation
16:35 - Coding Explanation
leetcode 41
This question was identified as an interview question from here: github.com/xizhengszhang/Leet...
#sorted #array #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[@ygwg6145]

In the first round, setting all values less than zero and greater than N with the default value N+1 simplifies the coding a lot.

[@Ford-ju9yr]

Why not 0? n+1 can be too much to store in case where n=maxInteger

[@VeetCoder]

@@Ford-ju9yr bruh, he using n + 1 anyways line 14

[@igboman2860]

Do people figure these things out by intuition or by studying?

[@jeffkirchoff14]

By Cyclic Sort

[@surendharv795]

kzbin.info/www/bejne/kJ_SpGaDrrGCh6s @Igbo Man Refer this....

[@soumyadeepdas1536]

The 3rd approach can't be intuitive i believe, you gotta know it at first. The best I came up with was sorting and hashing

[@learningwithcharan]

I am also having this doubt when I am able to see this kind of solution

[@AffairWithGeo]

​@@soumyadeepdas1536😅😅 me too

[@ZQutui]

Thanks for the content. It's the best channel with algorithm explanations. It is explained so clear

[@touwmer]

Man, this is 1000 times better than the official solution from leetcode Premium.

[@paularah2664]

I paused and solved this problem about 4 mins into the video. You have an amazing way of opening one's eyes to insights. Thanks for sharing your knowledge.

[@ameyakale6334]

The logic used to solve this problem is just insane. I love it ♥ Great explanation!

[@cedricchen6946]

This is the best solution and explanation I have ever found, I have been stuck in understanding index as a hash way, especially the “while” statement since I saw this question. And I harshly believe that the leetcode solution is not intuitive as it looks like

[@manubachhal404]

Finally found a best channel coding in phyton .

[@frida8519]

Dude, I couldn't do this hard question before, so I practiced a lot of the other medium questions and watched your videos. Then, I came back to this problem, and ended up figuring this out by myself! AHHHHH! TYSM!!!

[@3bood_kr]

You figured the second or first solution?

[@downhillskating101]

congrats!

[@vadimkokielov2173]

Thank you for all the good videos! One optimization I happened to come across that you missed. Your output range is actually not the length of the array, but the count of positive numbers in it -- a value you can compute very easily in your first loop.

[@HarmanFarwah]

What would happen if we have duplicate positive values in our array?

[@vadimkokielov2173]

We’re talking about the range. It’s a set already. If there are duplicate positives the range will be a little bigger. So what. The answer remains correct, and it’s still better than taking the length of the array

[@HarmanFarwah]

@@vadimkokielov2173 I understand now. Thank you

[@willaorito1149]

how is it an optimization? we are still looping thru the array right? and the first non negative number we get is the answer

[@allen724]

Thank you. For the edge case where the original value is a zero, in addition to setting something out of bounds, could we also just set it the actual value its represending? E.x. when 2 exists in [-1 , 0, ... ], could we set it to -2? That way we dont change the values in our input array since 2 is marked as existing already at some other place.

[@ngneerin]

This is what I came to comments section to comment

[@JackLaw3000]

This solution will be easier to read.

[@anuragkushwaaha2091]

This is exactly what I was also thinking of.

[@Jul835]

Best explanation I've found so far, thanks man

[@rentianxiang92]

Thank you! you are just awesome, please post more leetcode videos before I get accepted by Microsoft :)

[@lonen3rd]

Awesome explanation, I made a few modifications def first_positive(nums): n = len(nums) for i in range(n): if nums[i] < 1 or nums[i] > n: nums[i] = n+1 for i in range(n): if abs(nums[i]) > 0 and abs(nums[i]) 0: nums[abs(nums[i]) -1] *= -1 for i in range(n): if nums[i] > 0: return i+1 return n+1

[@linli7049]

Today I solved this problem and another problem called game of live, these two problems are difficult to figure out a solution with optimal space complexity because we need to store 2 pieces of information in a single figure, which is quite counter-intuitive.

[@mangalegends]

Sometimes I think I'm too stupid for leetcode lol. I never would have noticed that the solution would be less than or equal to the size of the array + 1. Apparently that's supposed to be obvious, but it wasn't obvious to me at all. Even knowing it now I still have to run through an example to confirm in my head that it's true

[@ehabteima]

It's impossible to come to the optimized solution unless you know it before hand.

[@anujpandey3101]

No

[@RahulPatel-hr4qe]

half of theleetcode is like that

[@AsmaeMouradi]

Thank you so much for all those videos you are really helping me. Waiting for more videos :)

[@ArjunKalidas]

This is the best and understandable explanation, I came across for this problem. Great job, please keep making more videos. Could you please make a video of "couple holding hands" problem on leetcode? Also, if you could explain the union find and connected component approach if you are taking that one in detail, that would be great.

[@MiguelLopez-xv1gf]

Thanks so much! you made it clear and easy to understand. One question, shouldn't like 8 be `if 1

[@soumyadeepganguly3719]

Beautifully done. I did it with a cycle sort type of method it got accepted but wasn't feeling good since it wasn't an O(n) solution. Got relief finally

[@sandeshsgowda5593]

Cycle sort too gives O(n) time in worst case. Since numbers are sent to correct position (index) with each swap, you'll be doing only n-1 swaps and each index is checked only once to confirm its at correct position. So total n-1+n => O(n) kzbin.info/www/bejne/gJfMn6uvqbmMfLM

[@Mr_SSK]

Amazinggggg, crisp and clear! Thank you so much! :)

[@akshatgupta107]

Such a good explanation. Thank you sir

[@rdgibbard]

Cyclic sort seems less convoluted: class Solution: def firstMissingPositive(self, nums: List[int]) -> int: i = 0 while i < len(nums): # set all 0 and negatives nums above the possible solution nums[i] = nums[i] if nums[i] > 0 else len(nums) + 1 # do a cyclic sort on nums ranging from 1..inf, skipping numbers # that are above the the possible solution correct_i = nums[i] - 1 if nums[i] < len(nums) and nums[i] != nums[correct_i]: nums[i], nums[correct_i] = nums[correct_i], nums[i] else: i += 1 # find the first number missing from its index for i in range(len(nums)): if nums[i] != i + 1: return i + 1 return len(nums) + 1

[@kamaleshs5324]

man the O(1) solution is brilliant and you explain it beautifully!

[@alanl5030]

Isn’t it technically O(n) because you have to iterate through the whole array

[@kamaleshs5324]

I meant the O(1) memory solution!

[@loba8924]

What a great explanation. Thanks.

[@c.4469]

Wow... Is it possible to come up with this solution without any help in a live coding session...? I think I never can :(

[@breakthecode8323]

You brilliantly explained it here

[@chandinivelilani3863]

Amazing Explanation!

[@aryanyadav3926]

Well explained!

[@Sophia-fw1rm]

but we can not use constant extra space how can we check it with a hashset?

[@sumithbabubare8297]

Thanks a lot for all the explanation

[@youngtraveler2799]

dude you are the best on explanation hard problems ... last solution I had to watch 6 times to get the idea ... anyway thanks

[@siningsun4160]

this idea is super clever and insane. thanks!

[@akashdey5637]

How does negative tell us that 2 exists in our input array?

[@rizzyhizzy173]

Great videos. May I ask what whiteboard program you're using to draw up the explanations?

[@NeetCode]

Thanks! I'm using Microsoft Paint 3D (free) 🙂

[@shijieding1316]

Hello sir, great video, I just have a question that at 8:30, why does negative tell us 2 exists?

[@Kavin2911]

ik its too late to reply, After 9:23 the array becomes [3,0,6,3] now we have to check if the element is present or not , general process is we marking (arr[i]-1) index element to negative which represents arr[i] is present (we are using index to check, as the answer lies between 1 to len(arr)+1)

[@orangethemeow]

I tried this solution but time limit exceeded. It worked by adding if nums[i] > len(nums) + 1 set it to 0 at beginning together with setting negative numbers to 0

[@fa11en1ce]

Is it really o(1) space complexity if you need the entire input array in memory? Sounds like it's a 3n,n time space complexity vs a n,n for the hashmap solution

[@andrewl8276]

Space complexity always refers to the EXTRA space being used, not including the input. If it included the input it'd be impossible to have O(1) space complexity, because the input growing would itself be increasing the space used.

[@mohitrsharma]

Instead of replacing negative integers by 0, we can replace them by n+1, where n=len(A). The algorithm will still work without the condition of checking A[val-1]==0.

[@OriMoscovitz]

11:20 There are so many things that are not clear I must say, you say since we know index 2 is negative we know that 3 exists in our input array, why? you don't explain why, and I don't get it. I'm rewatching and rewatching and yet can't figure it out the game with the indexes.

[@raiyanahmed3534]

this is such a beautiful solution

[@radicalengineer2331]

Neetcode is really neat and to the point : btw coding all in python, why you choose python for all problem solving?

[@fightapro]

Readability I’d assume

[@kevinbiazon8069]

Sir! you are a legend!!!!

[@AAA-uv1ny]

brilliant , thanks dude.

[@JohnIdlewood]

Is there algorithm where we can also restore the original array ?

[@adityasalian9806]

1000 iq play turning the array into a hashset. so slick!

[@misoren9645]

Thanks for the video. 7:55 "If I wanna know if the value 2 exists in our input array, i = 2 - 1 = 1, check the 1 index, check if it is negative, negative tells us that 2 exists in our input array, we don't know where it exists but we know it exists" ... Sorry that didn't make any sense for me. As in, why is that true and why are we doing that? Is there another explanation for that main loop, of checking the number as index and transforming it to negative? Thanks in advance

[@NeetCode]

Lets consider an example where Input Array is length=3. That means 1, 2, or 3 must be the smallest missing positive, except if all three of those values are in the input, then the result will be 4. By change the input array to be negative, I'm basically marking which of the values in [1, 2, 3] show up in our array. Notice how since our input array is length=3, I can map 1 -> index 0, 2 -> index 1, and 3 -> index2. Once we've marked every value that appears as negative at it's corresponding index. Finally, in the final loop we can iterate through the modified input array. The first non-negative value we see, will give us the result: for example, if index=0 is not negative, that means the value = 1 is going to be the first missing positive. If index=1 is non negative, that means value=2 is the first missing positive. If every value in the input array is negative, that means value=4 is first missing positive. (Remember, i mentioned above that 4 is the worst case solution).

[@xzex2609]

wow i lost it in the middle / but you are really great in describing problems

[@swarnimvarshneya6944]

but after changing negative values to 0 in the first loop how does the bug bother in last?

[@buzzClicksMedia]

But we are modifing the input , should we do that?

[@bouzie8000]

they expect me to figure out this solution in an interview? nuts. thanks for the video

[@saurabhdubey6345]

Sir what if array size is integer.max+1. In this case setting value as length+1 will also give false positive results ? What if we store integer.min, with this the abs for integer min can not become positive and we go easily marking the the zeros.

[@jollyjoker6340]

Python 3 has no maximum for an int. Max array size in Python on a 32 bit system is 536,870,912 while max int in Python 2 32 bit is 2,147,483,647 .

[@barry_allen558]

I am confused about the edge case, Why can't we set it to -1 ? Because when we iterate last time all we care is whether the array[element] < 0, Right we don't care about the value.

[@dheepthaaanand1133]

same doubt

[@shubhamrathore3735]

Because abs(-1) is 0 and we go and mark index 0 with a negative value but since -1 isn't in our array it will change the result we are looking for in the final loop

[@user-li7lc7pf5k]

I seriously love you. got my first interview next wednesday.

[@NeetCode]

Good luck! You're gonna do great 🙂

[@ryanmanchikanti5265]

Please let us know how it goes , all the best.

[@YeetYeetYe]

How did it go man?

[@enderaslan7998]

@@ryanmanchikanti5265 any good news??

[@dhruv3847]

Is there a solution where we could use bit manipluation(xor)?

[@jonaskhanwald566]

punctuality... perfect timing daily... in India its 9.30. Keep posting

[@aparnajadhav9197]

Are you sure this is working? because i wrote this exact same code in leetcode, but only 12 test cases passed :(

[@iharshgarg]

wow.. that was really smart way to store information in the given array itself without creating a new array.. wtf!!

[@WaldoTheWombat]

Haven't watched the video yet, but can't we just do quick sort while keeping a variable called min_positive which we will always compare the the current number we are sorting?

[@xuwang9205]

sorting need at least O(nlog(n)) time. The question requires to solve in O(n), which makes it a hard question.

[@mingjuhe1514]

Thanks!

[@amrholo4445]

really thanks a lot 💕💕

[@AndrewSmith00000007]

I'm not sure why missing line 8 (20:41) was a bug. If an element is a neg value, that means we've already changed the sign and the num exists. We don't need to execute "if" scope. Otherwise, it's just redundant.

[@binit1992]

because we are turning values negative down in this loop and a value could come as negative. Not doing this may miss some number that were actually positive , but flagged as negative to mark that particular index for third loop

[@orellavie6233]

I don't understand why we need to absolute the A[i]... If a one loop before it made every value greater or equal 0.. Other than that, great answer

[@krateskim4169]

Thank you so much

[@garywasherefirst]

insane explanation

[@andreykalmatskiy2656]

When you modify input, it is not o(1) space

[@sushantrocks]

Dude how do you manage when you need sorted containers in python. I know LC allows importing sortedcontainers 3rd party module - but any other way? Might be needed in interviews.

[@AmarjeetKumar-en1gk]

i am not able to understand for [1, 2, 0]. can anyone explain

[@igorf243]

Tasks like this are more like a lifehacks

[@sreevishal2223]

In the middle of the video the audio went out of sync which confuses your explanation, please check that out.

[@sarahcharlotte6681]

Every coding questions has different different logics. How to remember the logics and keep it in mind in interview

[@mdnoor4750]

the code is wrong in the second loop it should check if 1 = len(A):

[@junkoe3808]

I solved it differently with same memory and time complexity.

[@leul1407]

You are the best

[@hannanathar3627]

besttt explanation

[@furkanozyurt6845]

Thank you right man right your explanation right is very right clear right but I wish right you use right the word of "right" right less right.

[@jollyjoker6340]

20:20 There's no bug. You've already set all negative values to zero, the abs() does nothing.

[@thenerdprogrammer20]

bro there's the bug because in the iterations of for loop it is possible that we update a value to negative whose index is yet to come in the for loop and hence we have to take the absolute value of that when we reach its index

[@jollyjoker6340]

@@thenerdprogrammer20 Sure, but the if clause before the abs makes sure A[i] >= 1. Maybe that should have an abs too, can't really remember how this worked.

[@nzmike555]

Why not simply check if 1 is in the array first? If 1 is not present then it will be the answer.

[@whys2016]

why not just put -2 in index 1 when it is the edge case? that's easier than computing the out-of-bounds index.

[@sanassets8367]

because then 2 will be found in the array afterwads, it may have been the smallest positive missing.

[@aashitAgrawal]

solution was indeed very smart

[@devstuff2576]

Why not start with 0! Look for 1, if found, look for 2, etc . Then add 1 to the result when done looping! No need to sort!

[@dingus2332]

Hi homies , I think my solution is more intuitive , it uses same logic as Neetcode , almost #My Solution -> #Marking 0 and neg elements with len of more than the array so that , it skips when outbound for i in range(len(nums)): if nums[i] < 0 or nums[i] == 0 : nums[i] = len(nums) + 1 for n in nums : n = abs(n) #Dont consider length of more than the array (they cant be mapped) if n > len(nums): continue if nums[n - 1] < 0 : #Already visited then move on and ignore continue #Mark as visited , if can be mapped with the array nums[n - 1] = -1 * nums[n - 1] for i , n in enumerate(nums): if n > 0 : #Not visited return i + 1 print(nums) return len(nums) + 1 #Does not have a missing integer in the indexes of the array , so first missing integer must come after the array , which would be the len(nums) + 1 itself

[@suyashrahatekar4964]

How tf am I supposed to come up with that logic? I'm no Einstein.

[@anubhavsinha9526]

can someone explain why he did i-1 and made it negative for a value, doesn't make sense, out of nothing

[@amangaur4231]

Man you are Awesome :|o

[@rahulranjan7567]

It is so much similar to Pigeon Hole algorithm. Correct me if I am wrong

[@ngoctang6925]

This solution is great but I find it slower and takes more memory than a short and easier to understand solution. Can I ask why is that?

[@m.kamalali]

it beats 97 in memory and 75 in time

[@ngoctang6925]

@@m.kamalali I agree that it can beat more than 90 in memory but it only beats 50 at max for me

[@azamatik3]

you were able to explain the inexplicable, a u god?

[@T_tintin]

Insane

[@APudgyPanda96]

What an unbelievably stupid problem

[@matinzd]

I think you could just use set() function and then try to lookup via bruteforce.

[@josearbelo5263]

Why is it that I can solve this one in about two minutes but the easy ones take me hours. 😭

[@bh4541]

you lie

[@kedimnvfjnnvfjffurju]

Nicem didn't see the o(n)

[@fabianlopez1392]

the concept of constant space is inaccurate because you're changing the values of the input array which is normally not desirable

[@MOHITRANA-to7rf]

different LOGIC

[@ronifintech9434]

beautiful!!! but if FAANG think that those who can solve this question, are smart, they are SO WRONG!!! lol... I doubt anybody would be able to solve it optimally without having solved it!

[@edwardteach2]

U a God

[@jonaskhanwald566]

:) for i in range(1,len(nums)+1): if i not in nums: return i return i+1 :)

[@amyotun]

@jonas - since nums is the list, in operator will take O(N), N is length of nums and this is what we do not want O(N) in the inner loop. Agree?

[@NeetCode]

@@amyotun Yes, i believe thats correct

[@jonaskhanwald566]

@@amyotun agreed

[@rubinluitel158]

you will exceed time limit since your if statement is apparently o(n). another approach would be to put the list values into a hashmap and do your forloop for tht hashmap, time complexity will be o(n) but space complexity will also be o(n).

[@jonaskhanwald566]

@@rubinluitel158 Good approach. Its a popular interview question. The interviewer wont accept my approach for sure.

[@rohithbhandari7836]

This is the first hard question I solved by myself