First Missing Positive - Leetcode 41 - Python
Vložit
- čas přidán 2. 07. 2024
- 🚀 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. - Věda a technologie
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.
Why not 0? n+1 can be too much to store in case where n=maxInteger
Thanks for the content. It's the best channel with algorithm explanations. It is explained so clear
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.
Man, this is 1000 times better than the official solution from leetcode Premium.
The logic used to solve this problem is just insane. I love it ♥ Great explanation!
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
Best explanation I've found so far, thanks man
Finally found a best channel coding in phyton .
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!!!
You figured the second or first solution?
congrats!
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
Do people figure these things out by intuition or by studying?
By Cyclic Sort
czcams.com/video/Znos3MyLOQI/video.html
@Igbo Man Refer this....
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
I am also having this doubt when I am able to see this kind of solution
@@soumyadeepdas1536😅😅 me too
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.
What would happen if we have duplicate positive values in our array?
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
@@vadimkokielov2173 I understand now. Thank you
how is it an optimization? we are still looping thru the array right? and the first non negative number we get is the answer
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.
This is what I came to comments section to comment
This solution will be easier to read.
This is exactly what I was also thinking of.
Thank you! you are just awesome, please post more leetcode videos before I get accepted by Microsoft :)
Such a good explanation. Thank you sir
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.
You brilliantly explained it here
Amazinggggg, crisp and clear!
Thank you so much! :)
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
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)
czcams.com/video/JfinxytTYFQ/video.html
Amazing Explanation!
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
What a great explanation. Thanks.
Well explained!
Thank you so much for all those videos you are really helping me. Waiting for more videos :)
It's impossible to come to the optimized solution unless you know it before hand.
No
half of theleetcode is like that
this idea is super clever and insane. thanks!
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
Thanks so much! you made it clear and easy to understand.
One question, shouldn't like 8 be `if 1
Thanks a lot for all the explanation
brilliant , thanks dude.
this is such a beautiful solution
man the O(1) solution is brilliant and you explain it beautifully!
Isn’t it technically O(n) because you have to iterate through the whole array
I meant the O(1) memory solution!
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.
Sir! you are a legend!!!!
dude you are the best on explanation hard problems ... last solution I had to watch 6 times to get the idea ... anyway thanks
Wow... Is it possible to come up with this solution without any help in a live coding session...? I think I never can :(
really thanks a lot 💕💕
Thank you so much
Thanks!
1000 iq play turning the array into a hashset. so slick!
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
insane explanation
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.
but we can not use constant extra space how can we check it with a hashset?
How does negative tell us that 2 exists in our input array?
You are the best
besttt explanation
Neetcode is really neat and to the point : btw coding all in python, why you choose python for all problem solving?
Readability I’d assume
Hello sir, great video, I just have a question that at 8:30, why does negative tell us 2 exists?
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)
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
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.
When you modify input, it is not o(1) space
Tasks like this are more like a lifehacks
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
But we are modifing the input , should we do that?
Is there algorithm where we can also restore the original array ?
solution was indeed very smart
wow i lost it in the middle / but you are really great in describing problems
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
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).
wow.. that was really smart way to store information in the given array itself without creating a new array.. wtf!!
I solved it differently with same memory and time complexity.
but after changing negative values to 0 in the first loop how does the bug bother in last?
punctuality... perfect timing daily... in India its 9.30. Keep posting
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.
same doubt
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
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.
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 .
I seriously love you. got my first interview next wednesday.
Good luck! You're gonna do great 🙂
Please let us know how it goes , all the best.
How did it go man?
@@ryanmanchikanti5265 any good news??
Is there a solution where we could use bit manipluation(xor)?
Great videos. May I ask what whiteboard program you're using to draw up the explanations?
Thanks! I'm using Microsoft Paint 3D (free) 🙂
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.
Every coding questions has different different logics. How to remember the logics and keep it in mind in interview
Are you sure this is working? because i wrote this exact same code in leetcode, but only 12 test cases passed :(
Man you are Awesome :|o
they expect me to figure out this solution in an interview? nuts. thanks for the video
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?
sorting need at least O(nlog(n)) time. The question requires to solve in O(n), which makes it a hard question.
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!
i am not able to understand for [1, 2, 0]. can anyone explain
Insane
In the middle of the video the audio went out of sync which confuses your explanation, please check that out.
20:20 There's no bug. You've already set all negative values to zero, the abs() does nothing.
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
@@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.
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.
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
It is so much similar to Pigeon Hole algorithm. Correct me if I am wrong
the code is wrong in the second loop it should check if 1 = len(A):
What an unbelievably stupid problem
you were able to explain the inexplicable, a u god?
How tf am I supposed to come up with that logic? I'm no Einstein.
why not just put -2 in index 1 when it is the edge case? that's easier than computing the out-of-bounds index.
because then 2 will be found in the array afterwads, it may have been the smallest positive missing.
Why not simply check if 1 is in the array first? If 1 is not present then it will be the answer.
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
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.
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?
it beats 97 in memory and 75 in time
@@m.kamalali I agree that it can beat more than 90 in memory but it only beats 50 at max for me
I think you could just use set() function and then try to lookup via bruteforce.
Nicem didn't see the o(n)
different LOGIC
can someone explain why he did i-1 and made it negative for a value, doesn't make sense, out of nothing
U a God
Why is it that I can solve this one in about two minutes but the easy ones take me hours. 😭
you lie
:)
for i in range(1,len(nums)+1):
if i not in nums:
return i
return i+1
:)
@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?
@@amyotun Yes, i believe thats correct
@@amyotun agreed
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).
@@rubinluitel158 Good approach. Its a popular interview question. The interviewer wont accept my approach for sure.
the concept of constant space is inaccurate because you're changing the values of the input array which is normally not desirable
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!
This is the first hard question I solved by myself
Why we can't just create hash table just by removing last element in array and adding it to hash?
We will not use extra memory and we will not need all this sophisticated things.