DEV Community ๐Ÿ‘ฉโ€๐Ÿ’ป๐Ÿ‘จโ€๐Ÿ’ป

DEV Community ๐Ÿ‘ฉโ€๐Ÿ’ป๐Ÿ‘จโ€๐Ÿ’ป is a community of 966,155 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Create account Log in
codechunker
codechunker

Posted on

Solution to Leetcode's Flood Fill Question (interesting Question)

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

problem description

Question Explanation

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 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.

Top comments (0)

๐ŸŒš Life is too short to browse without dark mode