Notes on Rotten Oranges Problem

Hello guys welcome back to TechDoze and in this video we will see the rotten oranges problem. So let us look at the problem statement. The problem says that we are given a basket of oranges in this case it will be denoted by using a 2d matrix. Now this basket is containing three types of oranges. First one is a rotten orange, second one is a fresh orange and third one indicates the empty space. that is wherever you see zeros will indicate that this is a vacant space. Now a rotten orange can make all its neighboring oranges rotten in just a single time frame. We consider only four directions for adjacency that is up, down, right and left. The diagonal elements will not be considered as a adjacent element. Okay, so we need to calculate in how much time can all oranges in this basket rot, if it is possible to rot all oranges. otherwise if it is not possible to rot all oranges then you just return minus one so this is the entire problem now in this case you can see that in the first time frame this two will rot this one so this one will become two and this one will also become two since they will be rotten in the same time frame this two will rot the left and the down oranges so this will become two and this will also become two so this all things happen in just a single time frame So, one time frame has passed and the adjacent oranges have now been converted to rotten oranges. Now, you can see that we are left with here one only. And since this two is adjacent to one, so in the next time frame, this two will rot this orange and it will become two. Now, in the next time frame, this has become two and you can see that all the oranges in this entire basket has rotten. So, it took us two time frames in order to rot all oranges. So, in this case, we will return answer as two. Now let's say in our original basket instead of this one we had zero. So if we had zero here then these two cannot rot this one because it cannot pass through an empty space. So a rotten orange can only rot if the element is adjacent that is another fresh orange is adjacent and the diagonal elements are not considered as adjacent elements. So in this case if this element was zero. then it was not possible to rot all oranges since it cannot propagate through zero. So this would have been left as a fresh orange only. So we would have returned minus one in this case. So there are two cases. The first case is if it is possible to rot all oranges in the basket then we need to return the minimum time frames in which all the oranges can be rotten. Otherwise if it is not possible to rot all oranges then we just need to return minus one. So you can see that actually we are propagating breathwise. So a breadth first search algorithm will be very applicable to this problem. So we will be making use of the BFS approach in order to solve this problem. And you can see that there can be multiple starting points that is this two and this two will be operating parallelly. And this two will also be operating parallelly. That is we need to process in the breadth first search order. And also we have many points which we need to process parallelly. So in this type of situations what we need to do is we need to save all these points which needs to be processed parallelly in a sequence that is in a linked list. And then we can process each of these nodes one by one as if they have been processed parallelly. So for this type of problem we will make use of Q where we need to process many starting points that is many nodes parallelly. but we will just store it in a queue and we will process them sequentially as if they are processed parallely so you will understand just in a while what i am talking about so the node structure which i will be taking is the first one will be a time frame which will indicate the current time which has elapsed and we will also be storing the x and y coordinates of our oranges so this will be our structure of node now let us look at an example and solve it to get a better understanding Now this is a problem where we have 3 rows and we have 5 columns. Now I have already written the indices here. This is a basket of oranges containing fresh oranges, rotten oranges and empty spaces. The first step is to scan all the elements. We will scan all the elements and then we will store the location of the rotten oranges. So we have stored the location of rotten oranges as well as we will record the time frame as zero. since this is the starting point and no time has elapsed so you can see that i have stored x and y coordinates of all these twos that is all the rotten oranges now this is a queue and i have not joined it actually so you will assume that it is joined and in a queue the elements are added in rear and elements get removed from front okay now we will take each of the rotten oranges one by one and process it that is make all the adjacent oranges also as rotten So we will take out this first one. This first one is 0,0. Now all its adjacent fresh oranges will also be rotten. So when these two are rotten then we will just add them to our queue and then we will increase the time frame since after one time frame these are rotten. So I'll just add their indices that is the first one is having 0,1 and it is the time frame 1. because one time frame has elapsed after one time frame these will be rotten and for this one i will add one time frame and the index is 1 comma 0 so this will also get added our rear will also get updated once it has been popped it will never come back okay so our front will get updated now we will process the next rotten orange which is this one 0 comma 3 so this will be taken out from our queue this front will get updated and then we will process all the adjacent nodes so to the left hand side there is an empty space so nothing will be done to the right hand side there is one so this will get converted to two that is rotten and by the way these things are rotten now so this will be two now since this right one is also rotten we will just add it into our queue and this is after one time frame how i am writing this one this current nodes time frame which is zero current nodes time frame plus one will be added okay because after one time frame from the current node the adjacent node will be rotten so its index is 0 comma 4 so this will be also added to our q this rear will get updated this below one is also rotten orange so nothing will happen now we will take out the next rotten orange and we'll process it so this front will get updated and this is at 1 3 so this one up is also a rotten orange so nothing will be done down is also a rotten orange so nothing will be done left side you have a fresh orange so this will be made as two that is it will be made as rotten and we will add it into our queue so after one time frame this has happened and 1 comma 2 is its index value that is its coordinate value now the right orange will also be rotten so this will be made as 2 and its time frame will be added that is the current node's time frame which is 0 plus 1 so this will be 1 and index is 1 comma 4 this is the coordinate so this rear will get updated here this third node has also been processed now we process this fourth node fourth node is nothing but this one 2 comma 3 so this will be taken out this front will get updated and now you can see that up it's 2 so nothing will be done on the left hand side it's 0 so it is an empty space so nothing will be done on the right hand side it's 1 so this will be rotten it will be made as 2 and we will add this to our queue so the location is 2 comma 4 and the time frame is the current node's time frame which is 0 plus 1 so it will be 1 now this has also been added and rear will get updated to this new value this new node Now we will take out the next node which is this one 0,1 at 0,1 this 2. Now once we take out this node you can see that there is no adjacent 1. So nothing will be added. Now we take out this one 1,0 at 1,0 this 2 is taken out. There is only one adjacent orange which is to the down which is a fresh orange. So this will get rotten and its value will become 2 because this is now rotten. and what will we add here we will add the location 2 comma 0 and then we will add the time frame so the time frame of the current node is 1 and we will add 1 plus 1 which will be 2. so after 2 time frames this current node will be rotten now this has been processed so now we move on to the next node which is 0 4 0 4 will be taken out and you can see that adjacent to this 2 there is no other one so nothing will be done now we move on to the next node we will take out this node now it's at 1,2 now this 2 is also not having any adjacent 1 so nothing will be done we will go to the next node we will take out this 1,4 as soon as we take out any node then this front will get updated now at 1,4 you can see that we are talking about this 2 there is no adjacent 1 so nothing will be done now we take out this node and so front will get updated rear is also pointing to the same value now at 2 comma 4 we will take out this two there is no adjacent one so nothing will be done similarly this is the last node we take out this last node which is this two and there is no adjacent one so nothing will be done once you know that we can rot all the oranges then whatever is the time frame of the last node popped from this queue will be your time taken to rot all oranges so in this case The time taken will be 2. this is the time frame value for the last node now there can be two cases the first case is that it is possible to rot all oranges when it is possible to rot all oranges then this method will work and this last node's time frame will be your time taken to rot all oranges but then what happens if it is not possible to rot all oranges now let's say in our original matrix we had this first column as 2 1 1 now instead of this one if we had here let's say zero then it would not have been possible to rot this orange and when it is not possible to rot this orange then your answer should be minus one because it is not possible to rot all oranges why this has happened because to its up you can see that value is zero that is it is an empty space so rotten oranges cannot propagate through empty space and to the right hand side there is also zero and diagonal elements are not adjacent elements now in order to reduce the time complexity in the first step what we were doing is we were just scanning for twos that is the rotten oranges and we were adding them in queues now during this scan when we find a fresh orange that is one then we check if there is at least one orange that is either one or two lying to up down left or right if there are no oranges to up right down and left which has a value of one or two Then we can say that this orange is isolated and so it is not possible to rot all the oranges in this basket. So there can be many cases like you have this 000, 100 and this 100. In this case this one is having one as a down part and one is having this one as an up part. But then there are no twos. So it will not be rotten. So I hope you will be able to implement this method. This method takes a total time of order of n. Because in the worst case a single point can be traversed 4 times from its up part, down part, left part and also from right part. So there can be 4 different traversals. So we can have order of n time for this algorithm. I hope you are able to understand the rotten oranges problem. It is a very frequently asked question. if you have any type of doubt then feel free to comment below and i'll try to help you as soon as possible like and share our video and subscribe to our channel in order to watch more of this programming video see you in our next video thank you

Now this basket is containing three types of oranges. First one is a rotten orange, second one is a fresh orange and third one indicates the empty space. that is wherever you see zeros will indicate that this is a vacant space.

Now a rotten orange can make all its neighboring oranges rotten in just a single time frame. We consider only four directions for adjacency that is up, down, right and left. The diagonal elements will not be considered as a adjacent element. Okay, so we need to calculate in how much time can all oranges in this basket rot, if it is possible to rot all oranges.

otherwise if it is not possible to rot all oranges then you just return minus one so this is the entire problem now in this case you can see that in the first time frame this two will rot this one so this one will become two and this one will also become two since they will be rotten in the same time frame this two will rot the left and the down oranges so this will become two and this will also become two so this all things happen in just a single time frame So, one time frame has passed and the adjacent oranges have now been converted to rotten oranges. Now, you can see that we are left with here one only. And since this two is adjacent to one, so in the next time frame, this two will rot this orange and it will become two.

Now, in the next time frame, this has become two and you can see that all the oranges in this entire basket has rotten. So, it took us two time frames in order to rot all oranges. So, in this case, we will return answer as two.

Now let's say in our original basket instead of this one we had zero. So if we had zero here then these two cannot rot this one because it cannot pass through an empty space. So a rotten orange can only rot if the element is adjacent that is another fresh orange is adjacent and the diagonal elements are not considered as adjacent elements.

So in this case if this element was zero. then it was not possible to rot all oranges since it cannot propagate through zero. So this would have been left as a fresh orange only.

So we would have returned minus one in this case. So there are two cases. The first case is if it is possible to rot all oranges in the basket then we need to return the minimum time frames in which all the oranges can be rotten. Otherwise if it is not possible to rot all oranges then we just need to return minus one. So you can see that actually we are propagating breathwise.

So a breadth first search algorithm will be very applicable to this problem. So we will be making use of the BFS approach in order to solve this problem. And you can see that there can be multiple starting points that is this two and this two will be operating parallelly.

And this two will also be operating parallelly. That is we need to process in the breadth first search order. And also we have many points which we need to process parallelly.

So in this type of situations what we need to do is we need to save all these points which needs to be processed parallelly in a sequence that is in a linked list. And then we can process each of these nodes one by one as if they have been processed parallelly. So for this type of problem we will make use of Q where we need to process many starting points that is many nodes parallelly. but we will just store it in a queue and we will process them sequentially as if they are processed parallely so you will understand just in a while what i am talking about so the node structure which i will be taking is the first one will be a time frame which will indicate the current time which has elapsed and we will also be storing the x and y coordinates of our oranges so this will be our structure of node now let us look at an example and solve it to get a better understanding Now this is a problem where we have 3 rows and we have 5 columns.

Now I have already written the indices here. This is a basket of oranges containing fresh oranges, rotten oranges and empty spaces. The first step is to scan all the elements.

We will scan all the elements and then we will store the location of the rotten oranges. So we have stored the location of rotten oranges as well as we will record the time frame as zero. since this is the starting point and no time has elapsed so you can see that i have stored x and y coordinates of all these twos that is all the rotten oranges now this is a queue and i have not joined it actually so you will assume that it is joined and in a queue the elements are added in rear and elements get removed from front okay now we will take each of the rotten oranges one by one and process it that is make all the adjacent oranges also as rotten So we will take out this first one.

This first one is 0,0. Now all its adjacent fresh oranges will also be rotten. So when these two are rotten then we will just add them to our queue and then we will increase the time frame since after one time frame these are rotten. So I'll just add their indices that is the first one is having 0,1 and it is the time frame 1. because one time frame has elapsed after one time frame these will be rotten and for this one i will add one time frame and the index is 1 comma 0 so this will also get added our rear will also get updated once it has been popped it will never come back okay so our front will get updated now we will process the next rotten orange which is this one 0 comma 3 so this will be taken out from our queue this front will get updated and then we will process all the adjacent nodes so to the left hand side there is an empty space so nothing will be done to the right hand side there is one so this will get converted to two that is rotten and by the way these things are rotten now so this will be two now since this right one is also rotten we will just add it into our queue and this is after one time frame how i am writing this one this current nodes time frame which is zero current nodes time frame plus one will be added okay because after one time frame from the current node the adjacent node will be rotten so its index is 0 comma 4 so this will be also added to our q this rear will get updated this below one is also rotten orange so nothing will happen now we will take out the next rotten orange and we'll process it so this front will get updated and this is at 1 3 so this one up is also a rotten orange so nothing will be done down is also a rotten orange so nothing will be done left side you have a fresh orange so this will be made as two that is it will be made as rotten and we will add it into our queue so after one time frame this has happened and 1 comma 2 is its index value that is its coordinate value now the right orange will also be rotten so this will be made as 2 and its time frame will be added that is the current node's time frame which is 0 plus 1 so this will be 1 and index is 1 comma 4 this is the coordinate so this rear will get updated here this third node has also been processed now we process this fourth node fourth node is nothing but this one 2 comma 3 so this will be taken out this front will get updated and now you can see that up it's 2 so nothing will be done on the left hand side it's 0 so it is an empty space so nothing will be done on the right hand side it's 1 so this will be rotten it will be made as 2 and we will add this to our queue so the location is 2 comma 4 and the time frame is the current node's time frame which is 0 plus 1 so it will be 1 now this has also been added and rear will get updated to this new value this new node Now we will take out the next node which is this one 0,1 at 0,1 this 2. Now once we take out this node you can see that there is no adjacent 1. So nothing will be added. Now we take out this one 1,0 at 1,0 this 2 is taken out.

There is only one adjacent orange which is to the down which is a fresh orange. So this will get rotten and its value will become 2 because this is now rotten. and what will we add here we will add the location 2 comma 0 and then we will add the time frame so the time frame of the current node is 1 and we will add 1 plus 1 which will be 2. so after 2 time frames this current node will be rotten now this has been processed so now we move on to the next node which is 0 4 0 4 will be taken out and you can see that adjacent to this 2 there is no other one so nothing will be done now we move on to the next node we will take out this node now it's at 1,2 now this 2 is also not having any adjacent 1 so nothing will be done we will go to the next node we will take out this 1,4 as soon as we take out any node then this front will get updated now at 1,4 you can see that we are talking about this 2 there is no adjacent 1 so nothing will be done now we take out this node and so front will get updated rear is also pointing to the same value now at 2 comma 4 we will take out this two there is no adjacent one so nothing will be done similarly this is the last node we take out this last node which is this two and there is no adjacent one so nothing will be done once you know that we can rot all the oranges then whatever is the time frame of the last node popped from this queue will be your time taken to rot all oranges so in this case The time taken will be 2. this is the time frame value for the last node now there can be two cases the first case is that it is possible to rot all oranges when it is possible to rot all oranges then this method will work and this last node's time frame will be your time taken to rot all oranges but then what happens if it is not possible to rot all oranges now let's say in our original matrix we had this first column as 2 1 1 now instead of this one if we had here let's say zero then it would not have been possible to rot this orange and when it is not possible to rot this orange then your answer should be minus one because it is not possible to rot all oranges why this has happened because to its up you can see that value is zero that is it is an empty space so rotten oranges cannot propagate through empty space and to the right hand side there is also zero and diagonal elements are not adjacent elements now in order to reduce the time complexity in the first step what we were doing is we were just scanning for twos that is the rotten oranges and we were adding them in queues now during this scan when we find a fresh orange that is one then we check if there is at least one orange that is either one or two lying to up down left or right if there are no oranges to up right down and left which has a value of one or two Then we can say that this orange is isolated and so it is not possible to rot all the oranges in this basket.

So there can be many cases like you have this 000, 100 and this 100. In this case this one is having one as a down part and one is having this one as an up part. But then there are no twos. So it will not be rotten. So I hope you will be able to implement this method. This method takes a total time of order of n.

Because in the worst case a single point can be traversed 4 times from its up part, down part, left part and also from right part. So there can be 4 different traversals. So we can have order of n time for this algorithm.

I hope you are able to understand the rotten oranges problem. It is a very frequently asked question. if you have any type of doubt then feel free to comment below and i'll try to help you as soon as possible like and share our video and subscribe to our channel in order to watch more of this programming video see you in our next video thank you

Transcript for:Notes on Rotten Oranges Problem

Transcript for:
Notes on Rotten Oranges Problem