Flood fill algorithm

Flood fill is the algorithm behind the “paint bucket” tool in MS Paint, Inkscape, and many other image editing software. The principle behind it, surprisingly, can be applied in a game such as Minesweeper (like revealing empty adjacent squares after clicking a blank tile). It can also be used in image processing to identify regions of the image with the same features. Let’s explore how this algorithm works, look at the process step-by-step, and implement it!

How it works

Before starting a discussion on how the algorithm works, let’s define our input: 2-D array. Each number in this array represents the pixel of an image. For simplicity, I’ll only pick 5 colors: 0 (transparent), 1 (red ), 2 (orange ), 3 (lime ), 4 (blue ), 5 (fuchsia ). In reality, though, images are actually represented by 3-D matrix, because every pixel consists of three components: red, green and blue. Additionally, every pixel can contain alpha value (transparency), for example in PNG images.

Each pixel has an X and Y coordinate, where Y is the row and X is the column of the 2-D array. The X-axis goes from left to right, and the Y-axis goes from top to bottom. For example, pixel (0, 0) is placed in the top left corner, and pixel (3, 5) is placed in the bottom right corner.

Here is how the simplest image will look like in our example:

This image has 4 rows and 6 columns, and in memory it will be represented by the following array:

[
  [1, 0, 0, 0, 0, 0],
  [0, 1, 0, 0, 2, 2],
  [3, 0, 0, 0, 0, 0],
  [3, 3, 0, 0, 0, 4]
]

Let’s now go through algorithm step-by-step.

Starting point

Algorithm begins with a coordinate of a starting pixel. It is chosen by the user of a program, for example clicking on a pixel in Paint or clicking on a square in Minesweeper.

Let’s select pixel (2, 3) as our starting point:

Expansion

Then, we need to recursively or iteratively visit all of the neighboring pixels. This is where we can choose what pixels we are considering neighboring. For example, considering only pixels in the same row or column, or also diagonal pixels.

Here’s all of the neighbors of (2, 3) highlighted when performing 4-way expansion:

Here’s all of the neighbors of (2, 3) highlighted when performing 8-way expansion:

Boundaries

Expansion stops when we reach a pixel that has a different color or coordinates go out of bounds of the image.

Here’s an example of resulting image with 4-way expansion:

There are a couple of choices we can make when implementing this algorithm. We already discussed one of them (when talking about neighbors). The second choice we can make is how we’ll iterate over all of the pixels, that satisfy a given criteria: with DFS (depth-first search) or BFS (breadth-first search). Let’s explore both of them, how they work and implement them.

But before we start, let’s define a type and constant that will be used in both implementations:

type Pixel = {
  row: number;
  col: number;
};

const DIRECTIONS = [
  [-1, 0], // up
  [0, 1], // right
  [1, 0], // down
  [0, -1], // left
];

DFS Approach

The defining characteristic of the DFS is that before visiting a next neighbor, we first visit all of the children of the current node. So, from the previous example, we will visit pixels in the following order:

1:  [ 2, 3 ]
2:  [ 1, 3 ]
3:  [ 0, 3 ]
4:  [ 0, 4 ]
5:  [ 0, 5 ]
6:  [ 0, 2 ]
7:  [ 1, 2 ]
8:  [ 2, 2 ]
9:  [ 3, 2 ]
10: [ 3, 3 ]
11: [ 3, 4 ]
12: [ 2, 4 ]
13: [ 2, 5 ]
14: [ 2, 1 ]
15: [ 0, 1 ]

Let’s number all of the painted pixels in the order that they are visited from the example before:

Here’s an implementation of this approach:

function floodFillDFS(
  image: number[][],
  startRow: number,
  startCol: number,
  color: number,
): number[][] {
  const n = image.length;
  const m = image[0].length;

  if (image[startRow][startCol] === color) {
    return image;
  }

  const startColor = image[startRow][startCol];

  function dfs({ row, col }: Pixel) {
    if (
      row < 0 ||
      col < 0 ||
      row >= n ||
      col >= m ||
      image[row][col] !== startColor
    ) {
      return;
    }

    image[row][col] = color;

    for (const [dr, dc] of DIRECTIONS) {
      const [nextRow, nextCol] = [row + dr, col + dc];
      dfs({ row: nextRow, col: nextCol });
    }
  }

  dfs({ row: startRow, col: startCol });

  return image;
}

DFS approach relies on recursion to visit all of the neighbors of the current pixel.

There is also a nice little trick that I’ve utilized here: the DIRECTIONS array. Consider the code without it, it would have looked something like this:

dfs({ row: row - 1, col }); // up
dfs({ row, col: col + 1 }); // right
dfs({ row: row + 1, col }); // down
dfs({ row, col: col - 1 }); // left

This code is essentially doing the same, it visits all of the neighbors, but in my opinion, approach with DIRECTIONS array is better, because it looks cleaner, and when we need to change what neighbors we consider, we can just update this array, without rewriting the code.

Here is an interactive playground with the 10x10 image:

In this playground, you can select a fill color, click on a pixel, and observe in real-time how DFS performs a flood fill! You can also reset the image back to its initial state by pressing the “Reset” button.

BFS approach

BFS, on the other hand, visits all of the neighbors before moving to a deeper level. Again, taking our example, we will visit pixels in the following order:

1:  [ 2, 3 ]
2:  [ 1, 3 ]
3:  [ 2, 4 ]
4:  [ 3, 3 ]
5:  [ 2, 2 ]
6:  [ 0, 3 ]
7:  [ 1, 2 ]
8:  [ 2, 5 ]
9:  [ 3, 4 ]
10: [ 3, 2 ]
11: [ 2, 1 ]
12: [ 0, 4 ]
13: [ 0, 2 ]
14: [ 0, 5 ]
15: [ 0, 1 ]

Let’s number all of the painted pixels in the order that they are visited once again:

Here’s an implementation of this approach:

function floodFillBFS(
  image: number[][],
  startRow: number,
  startCol: number,
  color: number,
): number[][] {
  const n = image.length;
  const m = image[0].length;

  if (image[startRow][startCol] === color) {
    return image;
  }

  const startColor = image[startRow][startCol];

  const queue = new Queue<Pixel>([{ row: startRow, col: startCol }]);

  while (!queue.isEmpty()) {
    const { row, col } = queue.pop();

    if (
      row < 0 ||
      col < 0 ||
      row >= n ||
      col >= m ||
      image[row][col] !== startColor
    ) {
      continue;
    }

    image[row][col] = color;

    for (const [dr, dc] of DIRECTIONS) {
      const [nextRow, nextCol] = [row + dr, col + dc];
      queue.push({ row: nextRow, col: nextCol });
    }
  }

  return image;
}

I’ve used datastructures-js/queue for a Queue implementation. Note that queue.pop() is removing items from the front, instead removing them from back in plain JS array.

In the BFS approach we visit all of the children iteratively, and that can be a plus on a very large images (imagine getting a stack overflow error in paint). But otherwise, two approaches are almost identical.

Here’s an interactive playground with 10x10 image:

In this playground, you can select a fill color, click on a pixel, and observe in real-time how BFS performs a flood fill, and compare it with DFS that you saw previously. You can also reset the image back to its initial state by pressing the “Reset” button, just as in example from before.

Conclusion

Flood fill is a deceptively simple algorithm with a wide range of practical uses — from graphics editors to games and image analysis. By starting from a single pixel and expanding outwards, either recursively with DFS or iteratively with BFS, we can quickly identify and fill connected regions of similar color.

While both DFS and BFS approaches achieve the same goal, they differ in performance characteristics. DFS is elegant and easy to implement with recursion, but may hit stack limits on large inputs. BFS is more memory-intensive but safer for deep fills.

Understanding how flood fill works not only helps with building graphical tools or solving programming puzzles, but it also offers a great opportunity to explore fundamental graph traversal concepts in a visual and intuitive way.