hey everyone welcome back to the channel i hope you guys are doing extremely well so today we will be uh solving the problem rotten oranges so does the problem state the problem states will be given a grid of dimension n cross m that means a 2d matrix will be given of size n cross m now they are saying that zero means empty one means the cell has fresh oranges and the cell is marked with two it means the cells have brought in oranges now you have to determine what is the minimum time required to rot all oranges that means you have to figure out what is the minimum time that you need in order to rot all the oranges so how will the oranges get rotten so if there is a rotten orange at any given cell by index i j it can rot all the other fresh oranges that are at up down left right in unit time if they are fresh now let's understand the question in depth so imagine this like because this is true this is a rotten orange and this is connected to this this this this and this well this is only a fresh orange so these fresh oranges will be rotten in the first second it says in one unit of time it will rot the neighboring guys only so after one unit of time this is the state of all the oranges okay and the next what will happen in the next step this guy has already rottened all his neighbors so there is this orange left this orange has this this this this this so this will rot in this and this so in time to in time to this orange and this orange will rotten all its neighboring oranges so it goes down rottens this goes down rottens this right now we have this guy here here here here so this is already rotten already rotten and this guy is zero which is an empty cell it does not have an orange so you cannot rot in it so apparently right after time equal to two these couple of oranges did rotten the neighboring oranges after that now these are the new two oranges so can i see this guy has no one yes but this guy has someone on the bottom no one over here no one over here no one over here but someone at the bottom so i can say a time equal to three this guy will be rotten perfect what about time right after this but this guy is the new rotten orange so this guy has something like this so this guy will be rotten now so at time equal to 4 this guy was rotten so what is the time that you required to rotten all the oranges that is 4 seconds or four unit of time is what your answer will be for this particular question so let's take another example so this is an example and if you see the in the starting there are three rotten oranges yes in the starting there are three rotten oranges so if i say at time equal to one second what will happen this rotten orange will rot in all its neighboring oranges this rotten orange will also uh rotten all its neighboring oranges this orange will also rot in all its neighboring oranges so what will happen is this guy has this neighbor this neighbor this neighbor out of this this is just the single fresh orange so it will rot in it now time for this this guy and it happens simultaneously like when this guy will rot in this orange this guy will rotate this and this simultaneously right so what will happen is now this guy will rotate this and this after this there is only one orange left which is this which is rotten this guy will be like something like this so it will be rotting this done so i can say right after one second this guy not in this this guy wrote in this and this guy wrote in this so apparently if you carefully see are there any fresh oranges left the answer to that is no so the answer is in one unit of time i was able to rotten all the fresh oranges that were there in the matrix so let's take one more example so if i see this example over here we just have a single rotten orange to start off with so this will be rottening this guy this guy and this guy so please rotten it rotten so this will be this case at time equal to one second right at time equal to two what will happen the new oranges that were rotten they will rotten so this was rotten they will rot in its neighborhoods which is this then this guy will rotten its neighborhoods no fresh oranges nothing to rotten then this guy will rot in its neighborhood no fresh oranges nothing to rotten so apparently at time equal to two these three guys rotten all their neighboring oranges right after this we have another guy left right so this guy does not have any done so at time equal to 2 is when we will last rotten it because after that there are no neighboring oranges to be rotten but even after this we see there is one guy left who is a fresh orange but is it reachable no it is not why because the movements are only like this so a rotten orange can only rot in someone at the top someone on the right someone on the bottom someone on the left you cannot rot in someone who is at a diagonal or is at a distance you need to be attached to them in only these four directions uh to get rotten so as of now i can say this is not possible and if it is not possible you return minus one as your possible answer so if i ask you a very simple question which algorithm should we use so we have two rotten oranges and i can say it does rotten its neighbor at the same time which is one second so it is similar to saying these guys were at a distance of one or at a level one so each of them got rotten at a similar stage and if you're visiting same level guys because this is at level one level one level one same level guys at same time what algorithm do you use bfs because this is the only algorithm that traverses level wise had you gone something like dfs what would have happened is it probably would have gone from here to here then to here then to here then to here then to here which would have taken you one second two second three second four second five second if you would have used dfs which is depth first search would have gone in the depth and you would have visited all the neighboring fresh oranges but you need to make sure you require minimum time over here it's not like you need to rot in all the oranges over here it is like you need to apply the minimum time and that is only possible if you move in the neighboring directions at an equal pace at an equal pace right so that is what we will do this is the intuition behind bfs algorithm because we want to rotten them simultaneously that is why something like in bfs algorithm will be used so do you remember the bfs algorithm yes you do what is the initial configuration yes it is a queue so you can always define a queue and in the initial configuration you can always say that over here we have couple of starting points or the number of starting points will depend on the number of rotten oranges present initially and these are the two rotten oranges which are present initially so if i just number them uh the row number will go like the first rotten orange is at two comma zero the next rot in orange is at zero comma two so you can easily just pass on this and remember this what is the other thing that we require a visited array so probably you can create a visited 2d matrix so go ahead and create a visited 2d matrix done over here you can say the two rotten oranges that you pushed in you can easily mark them as two done now i need the minimum time right i need the minimum time so what you need to do is you need to always say that hey listen when these guys started it was the initial time so you need to carry one more variable something like zero with these guys saying at a zero time this these were the guys who are rotten okay right after that what you'll do is you'll say okay two comma zero is the row or the cell number and the time is zero now if i go to two comma zero this is what it is now we go to its neighbors who are its neighbors these are its neighbors invalid invalid empty cell only one neighbor is having a fresh orange take up this neighbor take up this neighbor put it into the queue with the time of one second because you will be taking one more second then the previous time so you will put them into the queue at the same time make sure you rotten it over here done what's the next step that you'll do you'll take this is done the next thing we'll take 0 comma 2 and the time is again zero the time is again zero okay and now what you will do is you saw okay at zero comma two the time is zero okay so where is zero comma two here who are its neighbors this guy invalid this guy invalid this guy a fresh this guy a fresh so there are two fresh oranges so you'll just pick up those two fresh oranges first one being one two comma one so one two is the fresh orange which is this and the time is one second over here it is zero and one so you'll pick up zero and one and this will be one perfect this is also done at the same time please make sure you mark them as rotten next two comma one comma one the time is one now we are taking time equal to one probably you can keep a variable which keeps the counter of the maximum time so the maximum time as of now is one right the maximum time as of now is one so we have someone as two comma one where is two comma 1 this portion is 2 comma 1 over its neighbors this guy a fresh orange this guy a fresh orange this guy invalid and this is already rotten already rotten so i found two fresh oranges so go ahead and rotten them in the next second which is two and over here at two comma two under and make sure you mark them as visited perfect this is also done at the next you take one comma two comma one this is a time equal to one whereas one comma two let's write it one comma two is here already rotten invalid already rotated already rotten so there is no fresh oranges remaining so done with this as well next you get 0 comma 1 comma 1 where is 0 comma 1 comma 1 here were its neighbors already rotten already rotten because over here you can find that they are already rotten in the visited arrays so no more neighbors of this guy so this is also done next time you get one comma one comma two so you got someone who took two seconds so you can say the time to be updated to two seconds now at one comma one comma two again if you see this is already written this is already written this is already written this is already uh empty so you find already written by this so no one again this is also done the next step you get two comma two and the time is two so the time is already two so if you see two comma two up one already written invalid invalid already dotted so i can see this is also done at the end of the day i can say the queue turns out to be empty and i have always visited all the cells i've already visited all the cells so let's see did all the fresh oranges got rotten if we started rotting from these two let's see this was a fresh orange is it rotten yes this was a fresh orange is it rotten yes this was a fresh orange is it rotten yes this was a fresh orange is it rotten yes this was a fresh orange is it rotten yes so all the fresh oranges were rotten so i was able to rotten all the fresh oranges and what is the maximum time i took the maximum time i took was two seconds so this is going to be my answer if any of the fresh oranges were not rotten in the visited array you could have printed minus one you could have easily printed minus one so as usual i'll be coding the c plus plus code and you can find the java code on the left so that you can easily follow so what do we need at first we have the grid right so please just make sure you figure out the n m because that will be required going forward just make sure you figure them out okay fine n m has been figured out what is the next step that we did we always said get me all the rotten oranges and put them into the queue so what you can do is you can store them into the queue something like a pair so this guy will be storing the row column and then you can store the time so this is how you can have the queue it's basically going to store something like this okay it's over here the row column and over here the time so this is how the data structure looks like next you can always declare something like a visited array perfect so declare this visited array okay now what you'll do is you will be traversing across the grid and get all the oranges that are rotten so just travel and over here you can say if grade of i j is equal to equal to 2 that means it is rotten and if it in case is rotted i will say q can you just take these guys because these are rotten and a time zero please take them right so this is something which you will always do so once you have done this what is your job you also need to make sure that these guys are marked as rotten at the visited so this is also done right after this you need the time to be computed so initially you can keep it as this and now you know you will always write the bfs this is how the bfs is written and you can always get the first row as q dot first dot first and in q uh the front element is front so yeah that's how you'll get it right after this you can always get the column as q dot front dot first dot second again follow this particular data structure guys follow this particular data structure first dot first first dot second will be the time the time will definitely be something like q dot front i'll be at the second done after this you can do q dot pop once everything is done you need to visit all the neighboring guys so if i go back and write of all the neighboring guys we have a row column right so at the top at the right at the bottom at the left so at the top we have something like row minus one column at the right we have something like row comma column plus one at the down we will have row plus one column at the left we will have something like row comma column minus one correct so this is at the top this is at the right this is the bottom this is at the left so can i say there is a change of minus one and plus zero when we go at the top can i say over here there's a change of plus zero and plus one so if i probably write something as a del roll delta rho equal to like this can be an array minus 1 0 plus 1 0 and i can write delta column as something as 0 plus 1 sorry my idea plus 0 and minus 1 perfect and now can i say on the row if i add this which is minus one on the column if i add this i will get the topmost cap similarly if i on the row add zero which is row and if i add plus one column plus one i will get this guy similarly if i add these i'll get this similarly if i add this i'll get this can i see i can definitely say so what you'll do is you'll just simply create this delta guys it's very simple you can say d row and you can create something like 1 0 plus 1 0 and you can similarly create something like d column right and d column can also be have something like 0 comma 1 comma 0 comma minus one perfect this is how you can easily get the d row and d column so how many neighbors are there there are exactly four neighbors so you can easily traverse for them so what will be the neighboring row the neighboring row is going to be very simple it's going to be the initial row and the change which is 0 delta rho of i will be the neighboring column it's going to be the column plus the d column perfect so this is how you can easily write it please make sure you maintain variable namings because code quality is very very important right after this you can say okay is this valid okay is this valid okay is n column valid have a check always is n this valid once they are valid i need to check i need to make sure are they previously not rotten which is neighboring row neighboring column are you previously not rotten that means are you not visited previously if you are not and are you a fresh guy because if you're not a fresh guy or you are an empty cell i don't go are you a fresh guy if you are a fresh guy and if you are not rotten then you are one among me and i can easily put you in the neighboring row in the queue with an old timer increased right so the timer will increase at the same time i can say the visitor to say okay these are my guys can you just mark them as one once this is done i'm getting the time every time so every time you get the time just make sure you store the maximum because whatever maximum you take that is what you'll store so just make sure that over here if it is not a rotten orange mark them as zero because it is very very important that you initialize the visited one and once the queue is done you can return the timer but before that you need to do a check so before returning the time you need to check if all of these fresh oranges and oranges which were initially fresh where all of these converted into rotten or not if it is not something like if visited of ij is equal is not equal to two and and on this grid it is a fresh orange if all the fresh oranges have not been converted you return a minus one this is a check if it is not then you return the timer just make sure you take uh an array instead of vector because you need to define vector if you take like it'll be a messy stuff so keep it short this is now let's submit this now you might argue whatsoever why did you check at the end you could have applied a different logic where initially you can keep a count so what you can do slightly different is probably over here uh do something like grade of i j equal to equal to 1 and keep a count of fresh that's it so you can always keep a count of fresh over here and so if you have kept initially a count of fresh okay so what you can do is okay you've kept the count of fresh so every time you're getting a fresh orange you are pushing that into the queue correct so what you can do is you can just keep a count over here every time you are getting a fresh orange you are pushing that into the queue so the end if the counter is not equal to all the count fresh that means you did not push them into the queue or you did not touch so you can just return a minus one you can also do this and this will also be running fine so even if you submitted via this count fresh method it still runs fine so yeah these things you can do you might argue instead of visited i can use the grid only yes you can do that but i always say whenever some data is given to you do not alter it because in industry if someone is giving you a data to perform something you don't change the data and work an algorithm on it right just take this data and you work on it basically copy of it so that is why never ever alter something which is passed by reference or something like this because that is the data that is given to you okay so this is how the code will look like so if i talk about the time complexity or let's first talk about the space complexity we are using a queue so how many total nodes or total oranges it can have all the oranges can be rotten which will mean that we will have n cross m oranges so n cross m will be the space over here using n cross m over here as well to visit it so you can say that overall it's like n cross m as the space that we are using on an extra basis so the space complexity can be said to be n cross m but what about the time complexity we are at first running n cross m loop so n cross m then we know at total the q will run if all the oranges are rotten sorry all the oranges are fresh then it will run for n cross m because that will be the number of times you will put them into the queue so the queue will run for that and for every guy we are running four times so for every node like for all the nodes we will be running for four times this loop so again this can be aggregated to n cross m only that will be the time complexity if we aggregate this so guys i hope i was able to make you explain this tough question so just in case i was please make sure you like this video and if you're new to our channel what are you waiting for hit that subscribe button right away and yes if you haven't checked out our dp series and the hd sheet the links are in the description please make sure to check them out enjoy this let's wrap up this video and meet in the next one till then bye take care golden