hey everyone welcome back to the channel I hope you guys are doing extremely well so this is another lecture from the stripers A2Z DSA course just in case you're for the first time here this is world's most in-depth course when it comes to DS algo why do I say that for 55 modules by the end of the course should have sold more than 400 plus problems in DS I'll go you can go across the entire internet you can buy any of the paid courses none of them will be teaching you DS I'll go in such step something that I can give you as guarantee is once you complete this entire post you can clear any of the DSL grounds in any company in any part of the world so till now we have covered uh till this particular problem now in this video I'll be covering the problem set Matrix zeros now what does the problem State the problem States you will be given an N cross M Matrix n and M can be different can be equal now the Matrix only has zero and ones that means it's a binary Matrix your task is to find out zeros you have once you have figured out zeros so there is a zero over here what you do is you go to the entire column in which that zero exists you go to the entire row and you mark every one as zero you mark every one a zero done where is the next zero here so you go entire column entire row and you mark every one as zero done next where's the next zero over here so you go across the entire column and row and Mark every one as zero now remember one thing over here there's a catch if there's a zero here you go here Mark here Mark here Mark here but from this Mark zeros you do not do anything only whatever zeros are there during the initial time for those zeros you go for the rows and columns for those zeros you goes for the rows and columns nothing apart from them got it so this question comes up in an interview the first solution that will give to the interviewer should be of the Brute Force solution what is the Brute Force solution that you can think of that's let's do whatever is being told to us what has been told to us if there's a zero go across the entire column Mark everything as zero and go across the entire row and Mark everyone as zero so probably let's let's try doing this as the part of the group 4 solution so what we do is we're given this n cross M Matrix we will try to I trade on it and how do we iterate on Matrix we go like this like this like this like this and so on till here so let's try to do it so we start from here it's a one it's a one so one it's a one it's a one we don't do anything when there's a one and we find a zero the moment we find a zero what was the task if like the entire column is 0 and the entire row was zero so what we will do is we will go ahead and probably probably Mark everything as zero but is that the correct solution think of it once you've marked the array will look something like this and in the next step of traversal you will reach here and then for this 0 you'll Mark every one again as 0 right and then you'll get this 0 and you'll start marking this but that is a wrong solution because of this 0 you ended up turning this one to zero and when you are traversing you will find a zero here and you'll end up marking everyone a zero on this column which is wrong because over here there's a one so these people should not be zero so thereby you have to be careful you just cannot go and blindly Mark everyone as zero you cannot do that so what I will do is I will go through the entire column and I'll mark everyone as minus one rather yes I'll mark everyone is minus one so Market is minus one I'll Market is minus one I'll mark it as minus one anything apart from zero I'll just mark it as minus one done let's Now quickly do the next job so this one is this column is done now we will go for this row so let's minus 1 and then minus one make sure you do not Mark zeros as minus one because this 0 will again be responsible for marking it so if you mark it as minus one there will be an issue so for this one I've marked this I've marked this I'll move forward the moment I move forward to this we have a 0 so we'll go for this column and we'll go for this row so let's do it minus one again not do not mark this minus 1 and this particular row is done now we will start iterating we have a minus one device will not do anything had we marked for the zero zero we would have ended up marking this which would have been dropped one minus one zero okay we have a zero so entire thing and then this entire thing so this will be minus one rather minus one and this will be minus one perfect next this one makes this one makes this one next this one next this one once you have done this now what do you know for these zeros whoever was to be marked they have been marked minus one so let's do one piece of iteration mode yes let's do one piece of iteration more and what we will do is we'll just convert them to zeros now we will just convert them to zeros and once you have done this I can say this is my final array and this will be my Brute Force solution quite simple just you have to be careful it's not about doing what they have said because that might cause an issue so thereby we will just introduce something as minus 1 in The Brute Force solution so we have to write the code for the Brute Force solution so you know in order to Travis we first Travis from 0 to n then we Traverse from 0 to M this is how you usually Traverse in a 2d Matrix and then what you do is you say if there's a zero on that particular place we go to the ith row and Mark that that means this portion then we go to the column that means this portion and we mark it and you have to write these couple of functions separately so let's quickly write it so the macro function will be very simple it takes a row number and then iterates for the columns and in every i j which is non-zero do not Mark the zeros in all the non-zeros you can just assign minus one similarly there will be a column which takes the column number and it creates for every row and marks that column as minus one if it's a non-zero so this code will make sure that everything that is a zero in that particular column everything will be marked as minus 1 and in that particular row everything will be marked as -1 apart from the zeros got it so once we've done this what's the next job the next job is just to hydrate in The Matrix and whoever is -1 turn it into zero so let's quickly do it so this will be the final piece of code where we iterate in The Matrix and we say if it's a minus one please convert it into zero so what will be the time complexity of the Brute Force solution can I say over here it's n into n and inside can I say this is taking we go of N and this is taking big of n because there are two Loops that are running so thereby it's something like n into M into n plus M very important into n plus n plus you're again doing an iteration of n into m in order to initialize them to zeros so this is the overall time complexity and it's somewhere to the power of Q somewhere to the power of Cube if you carefully see this and into this will be somewhere near about the power of Q and the interviewer will not be happy with it and he will say that this is not accepted and that's when you move to the better solution so let's quickly check out the better one so we give a Brute Force solution to the interviewer which was taking a Time complex actually in the order of NQ and why was it taking a Time complexity in the order of n Cube because we were traversing in the array and that was taking n square like in the order of n Square n into F and then what we did was for every 0 we went across the entire column and the entire row and we marked every one as zero so this is where we were taking that extra time for going across the column and going across the row so what do we need to eliminate because if the interviewer is asking us to optimize the optimal solution will definitely not be n q we need to optimize this and in order to optimize we might be able to get an N square or somewhere around n Square that's for sure this is where we need to think what do we need to eliminate we need to eliminate this and we need to eliminate this how can I now can I say what was I doing I was going across and marking everyone as you I will not do that instead of that I'll think for this one to be 0 in the final Matrix for this one to be 0 in the final Matrix why would it be I'll be like if this entire column has a minimum of 1 0 can I say if it is the minimum of one zero or if this entire uh row has a minimum of 1 0 agreed because this zero will convert this to 0 even the 0 will convert but what I need is just one zero and so can I say if there's a 0 instead of going across the entire column I will say if there is a 0 I will mark it I'll mark this column because at the end of the day everyone will be 0 in this column that's for sure so I'll just keep a track this column is done and dusted at the end of the day everyone will be zero similarly if there's a 0 this row is done and dusted everyone will be zero at the end of the day so instead of marking them at the current time I'll say let's probably keep a track and by the end of the day I will mark it this is how my thought process will be so to have that thought process converted into algorithm what I'll do is I know that for the zero I'll have to mark it and for the zero I have to mark it so there has to be four column array correct which will keep a track if the problem is marked and there will be a four over here four size row array which will again keep a track if the row is marked or not so I'll go ahead and create a m size yes very important I will create a column array of M size because those many are the number of columns and I'll create a row array of n size over here and then I must same and what I'll do is initially I will Mark every one of them as 0 0 means they yet not touched and now we'll start iterating first no one no one no one no one you will not do anything when there's a one and then you go ahead and see this is zero so whenever there is a zero you know this entire column is done and dusted at the end of the day everyone will be zero so please go ahead and say I will mark it marking it means one perfect and you know everything in this row will also be marked three Market as one perfect one one one one zero gain zero means everyone in this column and everyone in this row go ahead and Mark it sale Market perfect next one one again a zero the zero means this one is marked and this one is marked so go ahead and mark it perfect next the zero means this one is marked and this one is marked next this done so what I've done is for every 0 I've ended up marking which columns and which rows will be zero now what I will do is I will do a reiteration yes I'll do a reiteration let's quickly do the rehydration so whenever we are at one we are like okay wait will I be a zero I will only be a zero if this or this is marked is this marked no is this marked no so I stay one I stay one perfect I will say one I'll only be zero if this was marked I'm like yes I'm marked so I'll end up getting zero perfect next ever one oh this is marked so I'll end up getting zero next one one not mugged not marked so stays next one not mugged but marked here so this will be a zero next zero nothing to do one marked so this will be a zero next one marked so this will be a zero next one Mark so this will be a zero next one marked this will be a zero zero nothing to be done this one marked this will be easier this one marked zero this one marked zero this one Mark zero this one already is zero so what we got to know was this entire thing got zero if you carefully see and every one over here got zero apart from these two elements apart from these two elements and this is how easily you can do it got it so how the Brute Force code look like we know we need a column of size M to keep a track so I'll mark every one as zero and we know we need a row size n to keep a track of every one of zero now I will start iterating so if you have to iterate on The Matrix first I'll go from 0 to n then I'll go from 0 to M perfect then what is the next job if that element at i j is 0 I know the row I the row I will go ahead and get marked as 0 and the column J will go ahead and sorry Mark this one rather marked as one both have been marked and this is how you can I trade and Mark it once you have done that you again reiterate yes you again reiterate from 0 to n and this time you convert the ones to zeros were marked you convert the ones to zeros to a mark so what you say is if you are marked if your row is marked or or your column is marked if anyone is marked I do not care U will be zero for short because the entire sorry the entire row is marked or the entire column is marked if that's the case you will be this and this is how the code will look like got it so in case you want to try out the problem the link will be in the description and if you want the C plus plus Java and python code all the links will be in the description remember one thing uh over here they're asking us to return a metrics that is when returning if it's a void function then you can just change to this particular Matrix which we are doing and we do not need to return anything so coming back to the iPad again what is the time complexity can I say this is taking we go of n cross M and so is this wherever the time complexity is because of 2 cross n cross M for sure what about space complexity the space complexity is nothing but Big O of N and B go of M for the two arrays that are using for hashing this is where the interviewer will not be happy because you're using an extra space and he will ask you to optimize the better solution and you will move to the optimal one over here can you optimize the time complexity we are already doing it in the order of n square and we know the minimum in order to Traverse a matrix can be n Square you cannot do better than that that's why we will be focusing to optimize the time complexity and let's get back to the Matrix we'll be taking a column and we were taking a row agreed so if I was taking a column and if I was taking a row if I have to optimize it what does that mean that means you have to do everything in the Matrix itself so what I'll start thinking is can I keep a track in The Matrix itself can I just probably keep a track in The Matrix itself and that's when I start thinking what if I say hey maybe instead of taking a row outside what if I consider the First Column to be my row like instead of taking here I moved it inside from in place I moved it inside so what I'm saying is rho R are the column of 0 will become my row which I was taking probably yes and I'll say probably instead of taking this I'll move it inside maybe because I have to do it in the Matrix so that's a possible solution the row 0 is what I will not consider as column of M size that's my first assumption but can I take it let's see if that's possible so what am I saying the things that I was marking here like for the zero if I was marking here instead of marking here I am taking this and I'll mark it here that's what I'm saying correct but is it correct it's not correct why because okay I understood you took the column inside and that's how it looks but you took the grow also inside and now there is one single point which acts as the same and if you remember the better approach there was a row here and there's a problem here and everyone was individual this point and this point were individual but if you take them inside what happens is this is one and this is one and this is a single point where it's a common point so what I'll say is it's about one point I'll apply my brain and I'll say okay probably let's keep the row as row so I'll keep the row as row perfect and the column I'll take till here I won't take the entire column I'll take till here but then I'll be like what will happen to this one like who will keep the track of this because instead of this what you are doing is you're just taking this so what happens to this I'll say okay this one is a single element no it's a single element I will probably extend this to something like this can I do this I'll call it as a column variable I just call it has a column variable can I call this because this is an extra part this is an extra part so the row stays as row and I take this much and for this since it is colliding put it into a variable now there is no Collision it works works fine for me at least so now what I'll do is I'll try to probably draw the figure it's something like this and then I go like this will look like and it's more like maybe I can call it as column 0 and Mark it as what and this will be my row do you agree you do right so this will be my rope the same Brute Force I'm trying to optimize look at the intuition okay now let's start hydrating and let's try to do the same things that we did but before that let's keep something in mind this 0 will Mark everything here and Mark everything here agreed this 0 will Mark everything here and Mark everything it agreed this 0 will Mark everything here and everything so if you remember so if you see everyone will be converted to zeros only apart from this corner guy keep this in mind that this Quantum guy will not be converted keep this in mind it will be very very useful in the next part when we figure some edge cases keep this in mind the corner is not converted okay let's start I'm creating in The Matrix we have a one right what happens to this one this one says I'm a one so I do not harm anyone let's move I'm the one I do not have I'm a one I'm a one I'm a one I don't know but he's a zero he's like what did I do I'll keep a track sell Market here I'll mark it here and I know who who is this stuff this guy who's this this one so I will now go and convert them to zeros perfect next I have a one one one one one zero this zero was marking it here and marking it here so instead of this I'll Market you perfect next one zero now this zero was apparently marking it here and was apparently marking it here in The Culinary so what will happen now instead of here it will Mark here and it's already a zero so it's okay and instead of here it will Mark here so this will make it zero perfect next we have a one we have a one we have a one so the iteration is completed once the iteration is completed what is the next job to convert all the ones two zeros were marked correct to convert all the ones who are zeros this is where you have to remember in the answer only this one was not converted so if I'm trying to convert this whom do I check I check in this and I check in this correct for this one I see the column 0 is 0 so this will be zero right because it's marked if you remember for this we will check this and this and the column 0 is 0. so this will be converted to zero but But Here Comes The Twist if you convert this to zero hypothetically just assume you converted this to zero and the twist is if you convert this to 0 what will happen is now when you go to this one when you go to this one okay this one will say I will be converted to zero if this is 0 or this is zero and what will happen is it will find here 0 and it will convert this to 0 which is wrong because this row means this so thereby you cannot start from these elements you cannot start from these you can keep them for later because as of now if you change the values that will impact the Matrix do not change their values Instead try doing from these places Instead try doing from these places do you understand I hope you did right so what I'll do is I will not touch them as of now and I will start going probably from here then to here then to here and then we can deal with this separately got it so let's start this one will be marked no it's a one but it's a zero so this will be marked perfect this one it's a zero it's Market next this one it's a zero it's a zero Market please do not do anything to the first rows and first columns please next is the one will it be no will it be yes next is already 0 next 0 next 0 why because over here next zero because here next zero so what I've done is I've converted each of them now it's time for the next okay so the last section of this algorithm and it's very important that you hear me out properly so do you remember one thing initially I told you this is the only one who was not converted to zero and everyone else would be converted to zero now tell me one thing you have solved this portion will you solve this portion at first or will you solve this portion at first let's analyze this portions answer is dependent on whom one is this and the other other one is this correct agreed or not you agree so this one is hymns and this one is one so it's dependent on this so if you solve this portion at first the value might change the value might change which might hamper this which might impact this so at first you will solve this portion then you will solve this portion now for this portion to be 0 this has to be 0 which is not the case so this stays as one for this this is already 0 and this is already 0 and we do not do anything else now for this portion to be 0 this one has to be marked and this one has to be marked and I see this is marked so this will be zero convert it to zero for this portion it's zero zero zero done so first you solve here here here here here here and you solve this because it is dependent on this then you solve this first do not solve this because if you change the values that will impact the Matrix this was the thought process behind this particular algorithm so let's quickly quote the optimal solution up and this was the better solution if you can see in the editor so when we remove this and I will just comment this off so we were initially using the column and we were initially using a row now instead of column if I go back to the iPad instead of column we will be using the row 0 which is the row 0. can I say the row 0 is this which is nothing but Matrix of the zero yes because this is 0 right Matrix of 0 is what we will be using so can I see the column is nothing but the Matrix of 0 and something the variable whatever is the variable and can I say the row is nothing but if I carefully see the row is nothing but the zeroth the zeroth which is Matrix of something of 0 because the rule keeps on changing but this stays constantive so can I say it's nothing but Matrix of something of 0 raiseable this is the first row that is the First Column which is taken as this perfect now over here if Matrix of i j is this what do we do we Mark the ith row and we Mark the jth polyp now we are marking the row which is row C rho is here so we'll just take this let's take this so we have the Ayah through so you'll see let's mark the I here through so I throw is this and we will say zero and what are we saying who is the jth column this one so I'll take this and this is the Matrix and you will say let's mark this but can we simply write this the answer to that is no why because if you remember this case it did Mark itself that is okay but it could not Mark in the column it could not Mark in the column and if you see wire what's the column that's the Matrix of 0 of something Matrix of 0 of something so remember if J is not equal to 0 then only you mark it otherwise yes otherwise what will you do you will say caller of zero can you mark yourself if your J is 0 Let's go back again if you are over here you do not mark it here it's not you mark it here got it do not Mark anything on this instead of go here so please go ahead and declare one more variable column 0 is equal to 1. perfect that so this is the marking that I've done after the marking what do we do let's analyze that whatever we do so after the marking once we mark this and this we started from here and then we vendor so it's more like I ignored the zeroth row and I ignored the zeroth column so just iterate without them so I'll be like I can I trade without them as well so you can you can again iterate from here that's okay or you can hydrate from here as well that is okay that is your case so I'll go ahead and say okay let's iterate without the you can hide it in the backward or frontward as your choice this as long as you're not touching our hash arrays I'm absolutely okay so what what will happen what will happen if this is a one I have to convert it the first check will be if Matrix of i j is not equal to zero then there might be a conversion for this I'll have to check here for this I'll have to check here so check for column and row so let's check first you have to check for column what's the column that's this let's pick it up or or what's the rule that's this sorry that's this let's pick it up say over here instead of this you will have a j over here instead of this you'll have I and if any of them is marked as 0 that means this element will go as 0 quite simple done Second Step done where we have marked everything after that what did we do first we Mark these three elements then we mark this so how will this three elements when will this three elements be zero when will this three elements be zero if this guy who has Matrix of 0 0 if this is 0 then everyone will be because it's dependent on this so the last step will be hey if Matrix of 0 0 is equal to 0 everyone in the column which is this Matrix of zero J everyone in the first row will be zero white simple and what about this one this one will be dependent on the column so please go ahead and say if column 0 is equal to equal to 0 what will I do I will do the same thing for inti equal to 0 I lesser than n i plus plus because everyone on this portion will be marked as 0 so I will go and say Matrix of 0 sorry Matrix of I and everything on the First Column will be 0 once you have done this you can return the Matrix now let's quickly go and run I hope it runs at once I'll be super happy oh I am quite simple the only way that you can write this is try to write this so that you don't get confused this is how I approach usually a code so what is the time complexity and into m and this overall is the total Matrix alteration n into n 2 into n into f are you we using any extra space probably yes for this column that's it that's it one variable and I was able to solve the problem in place within the Matrix itself so let's go back to the sheet and Mark this as done I hope you have understood all the three approaches and the build up to the optimal solution just in case you did please please do consider giving that like because it won't cost you anything but it will highly motivate me to make these kind of content and if you're new to our Channel what are you waiting for there's a bunch of content on our Channel please please do consider subscribing to us and yes to continue our tradition please do comment understood and if you haven't followed me on Instagram Twitter LinkedIn the links are in the description with this I'll be wrapping up this video let's read in some other video till then bye take care [Music] I will find the light