@@Ford-ju9yr 0 results in the edge case where we can't mark it as negative, we reduce some work by setting it to be an out of bounds positive number instead
hey guys, tell me one thingg while we checking the nums[i] , we dont even check the neg number ryt and wt is the use of tit then making it as zeroo, i think have a point but , i need ur's too
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.
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!!!
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.
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.
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
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
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.
Good solution. Suggestion: instead of setting only negatives to 0, you can just set negatives and 0 to len(a) - 1, which will save you the corner case work too. You also don't need to check you will go out of bounds in the left direction this way. I coded it without looking at your code, on my own and this is the solution I came up with, which I do think is better in readability. I can explain more if needed.
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
How in the seven hells are we supposed to find out/arrive at this "nobody knows right away" kind of solution in an interview? 😵💫😵💫😵💫 Nice explanation btw.
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
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
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.
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).
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
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.
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)
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) ruclips.net/video/JfinxytTYFQ/видео.html
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.
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.
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
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
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
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?
part with the abs value and paying attention to negatives etc confused me. Here is my solution which takes 42 ms and beats 61% of the solutions: def firstMissingPositive(self, nums: List[int]) -> int: nums_len = len(nums) for i in range(nums_len): while 0 < nums[i]
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.
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.
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.
Man, this is 1000 times better than the official solution from leetcode Premium.
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
@@Ford-ju9yr bruh, he using n + 1 anyways line 14
@@Ford-ju9yr 0 results in the edge case where we can't mark it as negative, we reduce some work by setting it to be an out of bounds positive number instead
hey guys, tell me one thingg while we checking the nums[i] , we dont even check the neg number ryt and wt is the use of tit then making it as zeroo, i think have a point but , i need ur's too
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.
yeahh, u r absolutley rytt!!!
Do people figure these things out by intuition or by studying?
By Cyclic Sort
ruclips.net/video/Znos3MyLOQI/видео.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
Thanks for the content. It's the best channel with algorithm explanations. It is explained so clear
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!
Finally found a best channel coding in phyton .
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.
The logic used to solve this problem is just insane. I love it ♥ Great explanation!
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
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
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.
Good solution. Suggestion: instead of setting only negatives to 0, you can just set negatives and 0 to len(a) - 1, which will save you the corner case work too. You also don't need to check you will go out of bounds in the left direction this way. I coded it without looking at your code, on my own and this is the solution I came up with, which I do think is better in readability.
I can explain more if needed.
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
How in the seven hells are we supposed to find out/arrive at this "nobody knows right away" kind of solution in an interview? 😵💫😵💫😵💫
Nice explanation btw.
here's how: abandon your hobbies, social life, well-being, and sideprojects for leetcode three months before your faang interview
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
I think 95% of the people who are not competitive programers would miss this. I feel exactly the same
It's impossible to come to the optimized solution unless you know it before hand.
No
half of theleetcode is like that
Wow... Is it possible to come up with this solution without any help in a live coding session...? I think I never can :(
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!
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
they expect me to figure out this solution in an interview? nuts. thanks for the video
Best explanation I've found so far, thanks man
Thank you! you are just awesome, please post more leetcode videos before I get accepted by Microsoft :)
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.
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).
I agree this statement made no sense... the array in the example doesn't even contain 2.
How does negative tell us that 2 exists in our input array?
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
but we can not use constant extra space how can we check it with a hashset?
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.
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)
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)
ruclips.net/video/JfinxytTYFQ/видео.html
dude you are the best on explanation hard problems ... last solution I had to watch 6 times to get the idea ... anyway thanks
Thanks so much! you made it clear and easy to understand.
One question, shouldn't like 8 be `if 1
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.
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
Is there a solution where we could use bit manipluation(xor)?
i wil never find that way to solve this solution by myself
Is there algorithm where we can also restore the original array ?
Tasks like this are more like a lifehacks
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
@@anujthakur05 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.
Thank you so much for all those videos you are really helping me. Waiting for more videos :)
In the second loop abs isn’t necessary all values will be 0 or more, what am i missing
But we are modifing the input , should we do that?
but after changing negative values to 0 in the first loop how does the bug bother in last?
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
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
When you modify input, it is not o(1) space
this idea is super clever and insane. thanks!
1000 iq play turning the array into a hashset. so slick!
wow.. that was really smart way to store information in the given array itself without creating a new array.. wtf!!
Great videos. May I ask what whiteboard program you're using to draw up the explanations?
Thanks! I'm using Microsoft Paint 3D (free) 🙂
Sorry to ask a basic question, I m a newbie..why are we converting array to hashset here? Can someone pls explain
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
Amazing explanation!!
Are you sure this is working? because i wrote this exact same code in leetcode, but only 12 test cases passed :(
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.
part with the abs value and paying attention to negatives etc confused me. Here is my solution which takes 42 ms and beats 61% of the solutions:
def firstMissingPositive(self, nums: List[int]) -> int:
nums_len = len(nums)
for i in range(nums_len):
while 0 < nums[i]
Forget about problem even the solution is making me insane
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.
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
You brilliantly explained it here
set s(nums.begin(), nums.end());
for(int i=1;;++i){
if(!s.count(i))return i;
}
i am not able to understand for [1, 2, 0]. can anyone explain
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??
I solved it differently with same memory and time complexity.
punctuality... perfect timing daily... in India its 9.30. Keep posting
Amazinggggg, crisp and clear!
Thank you so much! :)
man, this is so clear!!!
Every coding questions has different different logics. How to remember the logics and keep it in mind in interview
this is such a beautiful solution
Thanks for this!
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.
Well explained!
Such a good explanation. Thank you sir
really thanks a lot 💕💕
wow i lost it in the middle / but you are really great in describing problems
Amazing Explanation!
the code is wrong in the second loop it should check if 1 = len(A):
Thanks a lot for all the explanation
brilliant , thanks dude.
What a great explanation. Thanks.
It is so much similar to Pigeon Hole algorithm. Correct me if I am wrong
solution was indeed very smart
In the middle of the video the audio went out of sync which confuses your explanation, please check that out.
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
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.
How can a person get this solution without watching any tutorials and solutions?
How tf am I supposed to come up with that logic? I'm no Einstein.
Thank you so much
Sir! you are a legend!!!!
you were able to explain the inexplicable, a u god?
What an unbelievably stupid problem
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.
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 .
insane explanation
You are the best
can someone explain why he did i-1 and made it negative for a value, doesn't make sense, out of nothing
Thanks!
besttt explanation
Why is it that I can solve this one in about two minutes but the easy ones take me hours. 😭
you lie