Practicing recursion with the flood fill algorithm

Courtney — Mon, 17 May 2021 17:12:41 +0000

The Challenge

Remember Microsoft Paint? I remember one of my favorite ways to play with it was doing one continuous, overlapping scribble, and then using the "fill" feature to fill in the empty areas with color.

That's essentially what we want to do here, implement the "fill" feature in code, known as the flood fill algorithm. Given a 2D array representing a pixel grid, a pixel location, and a new color value, we'll change the location and all of the surrounding locations of the same color to the new color value.

Example input array:

const screenGrid = [[1, 1, 1, 1, 1, 1, 1, 1], 
                   [1, 1, 1, 1, 1, 1, 0, 0],
                   [1, 0, 0, 1, 1, 0, 1, 1],
                   [1, 2, 2, 2, 2, 0, 1, 0],
                   [1, 1, 1, 2, 2, 0, 1, 0],
                   [1, 1, 1, 2, 2, 2, 2, 0],
                   [1, 1, 1, 1, 1, 2, 1, 1],
                   [1, 1, 1, 1, 1, 2, 2, 1]];

In this example, if we changed the color of one of the 2s, we would expect them all to change, as they're all connected.

This is a pretty simple problem to implement if you want to practice recursion.

Pseudocode

Here are the steps I took in pseudocode. There are other ways to implement this, the purpose here is to show you my approach.

function paintFill(grid, x, y, newColor) {
    // determine the value at (x, y), and store in variable
    // change the value at that location to the new color value
    // check the values above, below, left and right of the current location
    // if the color value matches the current location's previous value, call the paintFill function with the new location
    // return the changed grid
}

You'll notice I'm storing the value of the color first, this is on purpose, as we'll be changing it, and we want the checks of the surrounding value to be made based on the prior value, not the new one.

Implementation

function paintFill(grid, x, y, newColor) {
    let currentVal = grid[x][y];
    // set currentVal to newColor
    grid[x][y] = newColor;

    // check top, bottom, left and right
    // if they match currentVal, call function with that val's coordinates
    // top
    if (x - 1 >= 0 && grid[x-1][y] === currentVal) {
        paintFill(grid, x-1, y, newColor);
    }
    // bottom
    if (x + 1 < grid.length && grid[x + 1][y] === currentVal) {
        paintFill(grid, x+1, y, newColor);
    }
    // left
    if (y - 1 >= 0 && grid[x][y-1] === currentVal) {
        paintFill(grid, x, y-1, newColor);
    }
    // right
    if (y + 1 < grid[x].length && grid[x][y+1] === currentVal) {
        paintFill(grid, x, y+1, newColor)
    }
    return grid;
}

// testing with sample data
const screenGrid = [[1, 1, 1, 1, 1, 1, 1, 1], 
                   [1, 1, 1, 1, 1, 1, 0, 0],
                   [1, 0, 0, 1, 1, 0, 1, 1],
                   [1, 2, 2, 2, 2, 0, 1, 0],
                   [1, 1, 1, 2, 2, 0, 1, 0],
                   [1, 1, 1, 2, 2, 2, 2, 0],
                   [1, 1, 1, 1, 1, 2, 1, 1],
                   [1, 1, 1, 1, 1, 2, 2, 1]];

const newBucket = paintFill(screenGrid, 4, 4, 3);

for (const item of newBucket) {
    console.log(...item);
}
/*
1 1 1 1 1 1 1 1
1 1 1 1 1 1 0 0
1 0 0 1 1 0 1 1
1 3 3 3 3 0 1 0
1 1 1 3 3 0 1 0
1 1 1 3 3 3 3 0
1 1 1 1 1 3 1 1
1 1 1 1 1 3 3 1
*/

In my implementation, after storing the current value and changing the value at the location to the new color value, I move on to the surrounding values. For the locations above, below, left and right I am checking that the location is valid, that the value at that location should be changed, and then calling the function with the appropriate arguments. My base case is hit when none of the preceding conditionals apply to the value at the current location, which returns the grid. You can view the resources for alternate implementations.

I enjoyed completing this problem, I found it to be different enough from the typical simpler recursion problems to make it interesting and fun to implement.

Resources

flood fill algorithm descriptions

same problem with alternative solutions

https://www.geeksforgeeks.org/flood-fill-algorithm-implement-fill-paint/

includes diagonals

https://www.hackerearth.com/practice/algorithms/graphs/flood-fill-algorithm/tutorial/

DEV Community: Courtney