Solution to Leetcode’s Flood Fill

This is an easy Leetcode 733 problem. See problem description below:

flood fill description

To get a clearer picture of what the question wants us to do, first, it will be better to break the multidimensional array elements to form a square-like structure e.g the picture below shows the break down of [[1,1,1], [1,1,0], [1,0,1]]:

splitting of array elements

Now that we have broken the elements into rows and columns as shown in the figure above, the explanation of the question is this; given a particular starting row (sr) and a starting column(sc) which is suppose to be the starting pixel and given a new color (newColor) which is to be used to replace, change that starting pixel (sr, sc) to the new color (newColor) and also change its neigbours (4-directional to the starting pixel which is of the same colour).

For example, assuming the circled number in the image above is the starting index, the image below shows exactly the steps that will be taken to flood fill:

flood fill transition steps

NOTE: The colored numbers/pixels are the neigbours (4-directional)of the circled numbers/pixels.

STEPS

So Step 1 starts from the middle as the starting pixel, changes itself to the new colour which is ‘2’ in this case. It checks its neighbours (left, right, top, bottom), replaces those that had the same number as the one the starting pixel had (which is 1)before it changed to the new colour (2). So it changes all the 1s to 2s as long as they are neighbours. it then moves the ‘batton’ to its left neighbour (1st column)to go through the same process.

Step 2, changes its top and bottom neigbours to 2 because those neighbours had the same number as its initial before itself was changed. NOTE that step 2 does not have a left neighbour.

Step 3 and 4 go through the same process.

if you noticed, the left and right neigbours can be considered as the columns while the top and bottom can be considered as the rows.

ALGORITHM

The first idea that comes to the mind in this kind of problem is Recursion.

We need to keep a track of the initial colour and then use recursion to go through all the paths.

The source code is shown below:

class Solution {
public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
if (image[sr][sc] == newColor) return image;

flood(image, image[sr][sc], newColor, sr, sc);

return image;
}

public void flood(int[][] image, int color, int newColor, int sr, int sc) {
if (sr < 0 || sc < 0 || sr >= image.length || sc >= image[0].length || image[sr][sc] != color) {
return;
}

image[sr][sc] = newColor;

int topRowNeighbour = sr - 1;
int bottomRowNeighbour = sr + 1;
int leftColumnNeigbour = sc - 1;
int rightColumnNeighbour = sc + 1;

flood(image, color, newColor, topRowNeighbour, sc );
flood(image, color, newColor, bottomRowNeighbour, sc );
flood(image, color, newColor, sr, leftColumnNeigbour );
flood(image, color, newColor, sr, rightColumnNeighbour );
}
}

Thank you very much for reading. Please leave a comment or suggestion.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store