Flood fill – Recursion or no recursion?

In this article we’ll look at a simple implementation of the classic algorithm “Flood Fill”. If you played with Paint application before then this algorithm should sound familiar.

It is used in Paint to literally paint an irregular form in a certain color. This works fine as long as there is no gap in the initial form.

In this article we will implement the algorithm in JavaScript on top of a 2D array (e.g. a matrix).

In other works, we will need to implement a function with the following prototype:

function fillMatrix(matrix, row, col)

The function will take as arguments:

• a 2D array with only 0 and 1 values. The 1 values are used to delimiter various regions inside the matrix
• row and col are the initial coordinates inside the matrix, from where we want to start our paint operation

The function is supposed to set to 1 all cells from a certain region (like in the example above).

Tip: If you want to take this challenge alone, please stop reading the article here and try to implement the algorithm. For debugging purposes we suggest to use console.table method to display your 2D matrix in the console log.

Let’s start the implementation.

First, we need to fabricate a 2D matrix. In some languages this is easily achieved via language constructs, but in JavaScript, the easiest way to achieve this is by writing a function that generate such empty matrix:

// Returns a matrix of specified number of rows and cols
function generateMatrix(rows, cols)
{
    var matrix = [];

    for(var row = 0; row < rows; row++)
    {
        var arRow = new Array(cols);

        for(var col = 0; col < cols; col++)
        {
            arRow[col] = 0;
        }

        matrix.push(arRow);
    }

    return matrix;
}

This function does the job. All you need to do is to specify how many rows and columns you need when you invoke it.

We are now ready to implement the flood fill method. As we hinted in the article title, we will implement two versions: one using recursion and one without the recursion.

Recursive version

// Flood fill algorithm implemented recursively
function fillMatrix1(matrix, row, col)
{
    if (!validCoordinates(matrix, row, col))
        return;

    if (matrix[row][col] == 1)
        return;

    matrix[row][col] = 1;

    fillMatrix1(matrix, row + 1, col);
    fillMatrix1(matrix, row - 1, col);
    fillMatrix1(matrix, row, col + 1 );
    fillMatrix1(matrix, row, col -1 );
}

Is that simple. The function tries to set the specified cell and if succeeds then it invokes itself for the neighboring cells.

The validateCoordinates helper is doing nothing else than verifying if some provided coordinates are in the range of the matrix:

// Returns true if specified row and col coordinates are in the matrix
function validCoordinates(matrix, row, col)
{
    return (row >= 0 && row < matrix.length && col >= 0 && col < matrix[row].length);
}

We leave up to the reader the exercise of wiring these functions together and execute them. Remember to use console.table to troubleshoot the matrix in the console log.

What’s wrong? When you’ll test this method everything will work just fine, as long as you’ll use small matrixes. But in the moment you generate a larger matrix (e.g. 1920x1080 or bigger) this algorithm implementation will fail with “Stack Overflow”!!!

Iterative version

It is pretty clear that one of the easiest way to fix the “Stack overflow” error is to switch from recursion to an iterative approach.

We can do this by simulating the CPU stack (used by recursion) with our own stack that is allocated by JavaScript in a different area of the memory (e.g heap).

// Flood fill algorithm implemented with a stack on the heap
// This algorithm will also work with big size matrixes
var fillStack = [];
function fillMatrix2(matrix, row, col)
{
    fillStack.push([row, col]);

    while(fillStack.length > 0)
    {
        var [row, col] = fillStack.pop();

        if (!validCoordinates(matrix, row, col))
            continue;

        if (matrix[row][col] == 1)
            continue;

        matrix[row][col] = 1;

        fillStack.push([row + 1, col]);
        fillStack.push([row - 1, col]);
        fillStack.push([row, col + 1]);
        fillStack.push([row, col - 1]);
    }
}

Go ahead and use also this function in your code and observe the results. Pretty cool, no? Our code is not crashing anymore.

Visual implementation

And since this algorithm is best understood when is implemented graphically, we took advantage of the graphical capabilities of codeguppy.com and implemented this is a simple program that draws the matrix on the screen in a visual way.

The program is fully implemented in the following playground:
https://codeguppy.com/code.html?FEGENxWUL8WX69OgFtO7

All you have to do is to press “Play” and play with the canvas.

Happy coding!