Today, we will solve lead code problem. Number 733, and it says flood fill. And it has been asked quite a few times in some interviews of Amazon and google, and it's one of the easier problems. So here the goal is that you are given, uh, an image, an image you can think of as a 2d grid of pixels. And here each pixel has some value some integer values. So this one integer, denotes, one color. So if you look at this image, you see that these all are zero.
So these all pixel are of same color. Zero is one of. The colors similarly, here this is zero.
These are three. And you see that these a few pixels are having color of 2 and these are connected. And here by connected, we mean, 4 neighborhood connectivity. There can be multiple definitions of connectivity.
So we have one central pixel. So four connectivity means this is a neighbor of. So this is this main pixel we are talking about these four are neighbors of this pixel in another definition. There can be eight connectivity, eight neighborhood. Connectivity, in that case, even the diagonal will be considered as connected. But in this problem, we will just see the four neighbor connectivity.
So let's say, you are asked to flood fill at this pixel. So you must have used some painting tools like ms, pen or some similar tool where you uh, take an ink. And you drop the ink somewhere. Then you see that some of the pixels which are connected to it. The pixel where you drop the ink and are of the same color as the pixel where you drop the ink. Those.
All will get the new color. So let's say, I drop the ink at 2, and I drop a green color, green, maybe any of these colors, maybe 1 0 3, we don't know. So if we drop ink at 2, we will see that 2 will become green for sure then we will see what are the pixels that are connected to it, which are of the same color as 2. So 3 is connected, but its different colors, which color will not change. Then this two is connected. And its color is same as the pixel 2.
So we change it to green as well. And then we look. At the connected pixels of this. And these two are the connected of the same color. So these two also get the color of green now in the right, this is of different color on the top and the last neighbor.
We see that it's of the same color. So we color it green. Now here we look at its neighbor, one, different color, two different color because earlier it was two now it is. Now it is. Green may be five. So again, it will be different color, top different color, right? Same color, too so make it green as.
Well, and now we look at its neighbor, it has become green. It is different color, different. So we stop. So this will be the output so how we will proceed. So we will be given one function, flood fill you will be given this image, which will be a 2d grid, and you will be given one row and column coordinates. For example, this cell denotes, two, comma, three, two, comma, two, sorry.
So you will be given this. And you are given a color, let's say, green, this will be an integer in place of this color. It will. Be some integer like 1 2 or 5. So let's run through this.
This example, so we come here. We see it's, same color as the color. We are trying to assign or not. So there may be a possibility that this is two already. But you are asked to color it with two. In that case, you will return straight away. Why?
Because all the neighbors, which are two, which will be the target color are already of the same color. So you will, you will be stuck in loop. So you's 2, you make it again 2. And then you look at its. Neighbor it's 2, so it's, the same color as this.
So we make it 2. And then we look at its neighbor. So you will again, find this 2 because this is same as the old color. So in that case, there is no point in proceeding. If the new color is same as the current color, we return straight away, but let's say, it's, not that case, then we will color two with green. We will look its neighbor, which are of the same color, the old color. Now this has five, but the old color was two.
So this never has two. We color. It green. Similarly, this neighbor this and this.
So this would be the output so let's write the pseudocode for this. So this is our color. So we will check if uh, this image, RC it's, same as this color. So already it was same color. So we return no point in proceeding further, otherwise let's define a function recursive function of fill. And you pass these things color, and we also pass old color. And here what we will do?
Ah, we will first assign it, new color, or this is color here. Then we will do fill. On its neighbor that is r, plus one, c and other things remain same and r, plus 1 c denotes.
If this is r and c r, plus c, denotes. This one exactly below, then we will do r minus 1 c. So same column, one row less. So it will be this. One next neighbor is this one.
So it will be in the same row. This is r, same row, one more column. So this will be RC, plus one other things remain the same. So I am not writing it. And the last neighbor will be RC minus 1, which is this neighbor. And ultimately, this will again. Look at.
It neighbors, and we will have a check here that old color should not be same as the current RNC values, same as this. So we will return in that case. So let's write the code for this quickly in c plus this. Then we will write in java and python as well. So if image are c equal to new color, then return image here. The return type is this vector, vector, int, which is same as the image. So we have to return the hint, otherwise let's define a function and pass on all the parameters and one new.
Parameter which is old color, if r is less than 0 simple bonds, check or c is less than 0. These are invalid indices. It can be possible. Let's say you reached here you called for this. And now r is 3 so it's. One of the neighbors will be here r plus 1 c. So this is more than the size.
Similarly, if you are on the edge, this edge, either top or left, it can be negative or are greater than equal to image dot size or c greater than equal to image. Zero dot size. So image dot size will be a number of rows. We go.
One level deep image, zero dot size will be a number of columns or old color is not equal to this image. RC. Then we return else, let's make it r and c on new color.
And finally, old color r, minus 1 RC, plus 1, c, minus 1 and same thing here, uh, it should be Sr and SC and old color is this one image r c. And finally, we have to return also, so we will return image. And here we are modifying the input image as itself. So we are not using any extra space for this and that's it that should work. So let's, try, oh. Image RC here, it's RSC in the input line, four.
So there is some runtime error. Maybe we are accessing some stack overflow on address I'm, not sure what is the error so let's log something here? What are the indices that are getting called? Okay? So possibly it's getting stuck somewhere.
And what is the test case? It's, one, one, two. So it calls for one, then two one, then zero one, okay, I got it. We are not changing the color here. So it will keep on doing this.
So we have missed the main thing of coloring it. Image r c equal to new color. This was the main step, which will do the painting we are not doing that. So now the color should change, and this will not be stuck in infinite thing. And it works for this case. So let's, go ahead and submit.
And the solution is accepted in c, plus so let's copy it for java. No more changes required. I guess let's see. And this works so let's submit. And the solution is accepted in java as well. Finally, we will write it in python 3.
And that's it. This would work. Okay, r is not.
Defined my Sr is fine here r is not defined. So this works in python let's submit. And the solution is accepted in python as well.
Dated : 18-Apr-2022