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.
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 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 ????
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
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!
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!
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!
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 !
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 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
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.
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
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.
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
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?
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.
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!
@@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. :)
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 ?
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?
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?
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)
@@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
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?
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.
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)
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.
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 ??
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.
@@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 :)
If you support me on patreon, you can get access to the private community discord. Check it out in the description if that is something of interest to you!
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
What a ridiculous problem lol. Can pretty much say I would have never thought of doing it this way. Thanks for the explanation!
lol yea, the optimized solution is definitely an "outside of the box" approach. Thanks for watching!
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.
Wow awesome glad to hear!
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.
Thanks man! I'm a visual learner myself so a whiteboard explanation makes the most sense haha
@@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 ????
@@Sumit-yn7dn that's why he is using a variable to check if 1 is present or not during the first traversal.
The best explanation ever. Thank you so much for explaining slowly with diagrams for each edge case
Glad it was helpful!
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.
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
I appreciate it man! It's a challenging problem for sure haha, thanks for watching!
The Tone of your voice makes me wanna continue listening forever .. so clear ..
Thanks for the awesome video .. ✨
after seeing the video problem looks easy, great explanation on whiteboard !!
Thank you!
Michael, I found gold again! This one
th-cam.com/users/maksrane100 check this too
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.
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!
Glad I could help!
Hope you are better now. Thanks for the video. Great explanation.
All better now! Thanks for watching!
Awesome idea handling negative numbers. This should be present in the leetcode solution.
Agreed, thanks for watching!
brilliant solution. I love the way how this problem reduced to cyclic sort
th-cam.com/users/maksrane100 check this too
Thank you!
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!
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!
Just awesome
extremely clear explanation not less than any professional
keep making videos
it helps us lot
thanks man
Thanks, will do!
you're a godsend man. amazing explanation throughout. thank you.
This is such a silly problem, Wouldn't have thought of this solution. Thanks a lot for your explanation.
lol yea it is a ridiculous question
that was the simplest solution i watched . Thank you!
Glad it helped!
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 !
Haha yea its a tough problem to get down to constant space. Thanks for watching, commenting, and subscribing!
Thank you so much for such an easy explanation. This just saved my day :). Keep making more such videos.
Anytime! More videos coming every week!
Damn! Saved your day? What really happened to your day? xD
You made it look so easy. Thanks a lot.
Glad it helped!
This solution was better than the leetcode solution article
This was super helpful and was explained very well. Thank you!
I'm so glad you found it helpful, more videos to come!
Man your explanation is brilliant. Awesome!!! Thanks, dude.
Glad it helped!
Beautifully explained.. keep it up brother
Thank you man!
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)?
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.
@@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
this was the best solution i have ever seen
Thank you so much!
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.
I do a check if 1 is not present before getting to the main part of the algorithm. So,
`if (containsOne == 0) return 1`
@@AlgosWithMichael Loud and clear. Thanks.
Nice, glad it helped!
great explanation Michael. you saved me a lot of time.
Glad I could help :)
Thanks, it's awesome solution!! have think about this case about 2 days haha
Great problem, and great explanation. Thanks!
Thank you very much!
Thank you this great explanation.!!!!!
Thanks
Great solution.. please keep posting hard problems like this
Glad you liked it! Thanks for watching.
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
Yea, it very tricky haha, thanks for watching!
this is better than the provided solution in LC which I couldn't understand.
Thanks, that was my goal!
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.
awesome explanation, keep going!
Thanks, will do!
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
Great explanation! Very helpful. Thanks!
Thank you!
Thank you so much. You explained it so well. Super helpful!
You're very welcome!
So well explained! Thank you so much!
Glad you enjoyed it!
good explanation. you opened my eye. thanks Man.
Glad to hear it!
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?
Super awesome ,very tricky problem
Yea it definitely is!
6:20 What if 1 wasn't already in the array?
Ohh nvm lol
[2, 2, 2, 2, 2] is it going to work?
That was an amazing explanation. Thanks
No problem, thank you for watching!
Why are we doing index+1 to search for the number value of index? in 11:29
Because index is 0 based, thus we must offset it. Thank you for watching!
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.
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!
@@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. :)
Anytime!
Great explanation. Please do more leetcode hard problems.
Thank you!
Explained very well.
Thank you!
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 ?
Thank you so much! I believe the problems are different in the sense of what values are allowed inside of the arrays.
@@AlgosWithMichael Yes you are absolutely right! Thank you for your reply!!
Great Explanation bro .
Thank you 🙂
Great explanation! Immediately subscribed after watching this video. Btw are you a student or a working professional?
I appreciate that! I currently work full-time as a Software Engineer.
@@AlgosWithMichael Your videos are very helpful! Keep up the good work 👍
May I know which company are you currently working for?
I work for a mid-sized company in LA, not a FANG or anything like that!
Hi thanks your videos are very nicely explained you got a lifetime subscriber for you .. please keep the good work
Thank you so much, that means alot!
Nice trick. Probably applicable to other problems.
Yep, this trick is definitely seen in a lot of array restricted problems.
Where can i get the code?
Amazing explanation bro.. keep it up!!
I appreciate it, thank you!
After watching the first 10 mins, this problem became an easy one.
Awesome, glad to hear!
can you post a link to the code please??
Bro, Thanks a lot .
You saved us.
Haha awesome, glad it helped!
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?
th-cam.com/users/maksrane100 check this too
best explanation thank you
th-cam.com/users/maksrane100 check this too
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?
Amazing explanation!
Thanks!
th-cam.com/users/maksrane100 check this too
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
Yea, it is a good solution, but I would imagine in an interview they would want the more optimized approach
Great explanation bro
Thanks man!
# Can we do this
for i in range (1,len(l)+1):
if i not in l:
print(i)
break
This doesnt run in O(n). The outer loop is O(n) and the "item in list" operation is itself an O(n) operation, so this runs in O(n^2).
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)
How am I sure there will be always 1 in my test case?
There won't necessarily always be a 1 in your test case, but it is an edge case you must handle if there is
This is awesome. Thanks Man
th-cam.com/users/maksrane100 check this too
Good solution ❤
What if 1 was the missing positive number. Wouldn't switch those to 1 mask that?
I do a check if the missing number is 1, it is an extra edge that is definitely a gotcha!
Hi MIchael, I have a doubt if you could clear. How it will behave for [-5, -4, -3] .
I believe 1 would be the returned answer
Awesome explanation. I have a question, why use a set? cant we just do Array.contains() ?
Set is o(1) lookup. Array.contains is o(n)
Thanks for the great explanation. Is there a name for this technique?
Not really. The solution to this problem is really unique haha. Thanks for watching!
th-cam.com/users/maksrane100 check this too
very well explained!
Glad to hear, thank you!
How did you get 0ms?
That sometimes happens on LeetCode
can you do a video on dice roll simulation leetcode
I will add to the list!
Please post more videos :)
More every week!
Why do you check the absolute value in step 2? You already turn all negatives into positive 1s in step 1...?
nvm, im dum
Haha naw it's a confusing solution
what happens for [0,1,2] -> 0 -1 = -1 wil come right?
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!
@@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
If you go to 19:27, I fix that mistake of not doing `
I was trying to do it of my own after watching your approach which confused me.. you are right ! Thanks for the video !
Gotcha, well thank you commenting and watching!
Will this still work if missing number was 1 itself?
Yes, I had to do an extra check to see if the missing number was 1 itself at 16:10. Thanks for watching!
very helpful. Thanks!!
You're welcome! Thanks so much for watching!
Why I'm hearing *Intelligence beat*
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?
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.
That was smart ; ) . Thank you!
No problem!
we can replace out of bound numbers by INT_MAX? then during second iteration if abs(nums[i]) is INT_MAX just continue?
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)
Yea I believe you could. However, I could see an edge case where a number in your array is INT_MAX. Thanks for watching!
Can you please solve leetcode 84- Largest Rectangle in Histogram. It is a hard problem and there is not good explanation on youtube
Yea sure 👍
@@AlgosWithMichael thank you
Is this a standard algorithm for this type of problems?
Not too sure honestly haha. This problem is very different from any other problem I have seen.
best explanation ...
I appreciate that, thank you
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?
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.
Haha yeah I messed up
@@AlgosWithMichael it was very helpful bro... Keep up the excellent work.
Great explain
Thank you so much!
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 ??
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.
@@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 :)
Thanks so much!
Awsome Dude ..best
No problem man!
Amazing
Thanks!
discord link?? pls
If you support me on patreon, you can get access to the private community discord. Check it out in the description if that is something of interest to you!
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