Practicing recursion with the flood fill algorithm
Tags: javascript, algorithms, recursion
Published: 2021-05-17 17:12:41

---
title: Practicing recursion with the flood fill algorithm
published: true
description: Implementing Microsoft Paint's "fill" feature in JavaScript.
tags: JavaScript, algorithms, recursion
---
## 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.

![Paint scribbles](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/st8rv5sq4f89kwibs6pi.png)

That's essentially what we want to do here, implement the "fill" feature in code, known as the [flood fill algorithm](https://en.wikipedia.org/wiki/Flood_fill). 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:
```javascript
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. 
```javascript
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

```javascript
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
* https://en.wikipedia.org/wiki/Flood_fill
* https://www.freecodecamp.org/news/flood-fill-algorithm-explained

#### 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/