Flood Fill

The problem. An image is a grid of numbers, each one a colour. Starting from the pixel (sr, sc), repaint it with color — and also every pixel connected to it (up, down, left or right) that had the same original colour, and every pixel connected to those, and so on. Return the image. It's the paint-bucket tool.

Example

image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2
->      [[2,2,2],[2,2,0],[2,0,1]]

image = [[0,0,0],[0,0,0]], sr = 0, sc = 0, color = 0
->      [[0,0,0],[0,0,0]]          (already that colour: nothing changes)

The pattern: traverse and count

This is the first and most common graph pattern. The grid is a graph — each pixel joined to its four neighbours — and the region to paint is everything reachable from the start through pixels of the original colour. So: start a walk at (sr, sc), step only onto pixels of the original colour, and paint each one as you arrive.

Painting a pixel is marking it visited: once it holds the new colour it no longer matches the original, so the walk never comes back. That's why one case needs care — if color already equals the original colour, painting changes nothing and the walk would loop forever. Check for it first.

1. DFS: paint, then recurse in four directions

1function floodFill(image, sr, sc, color) {2  const original = image[sr][sc];3  if (original === color) return image;        // already that colour: nothing to do (and no endless loop)4  const rows = image.length, cols = image[0].length;5  const paint = (r, c) => {6    if (r < 0 || r >= rows || c < 0 || c >= cols) return;   // off the image7    if (image[r][c] !== original) return;                    // another colour: the region ends here8    image[r][c] = color;                                     // paint it, which also marks it visited9    paint(r - 1, c);                                         // up10    paint(r + 1, c);                                         // down11    paint(r, c - 1);                                         // left12    paint(r, c + 1);                                         // right13  };14  paint(sr, sc);15  return image;16}

Time O(m · n), space O(m · n). Every pixel is painted at most once. The recursion can go as deep as the region is large — a whole image of one colour means m · n nested calls.

2. BFS: paint with a queue

The same walk with a queue instead of recursion, so a huge region can't overflow the call stack. Paint each pixel as it enters the queue, so it can't be added twice.

1const DIRS = [[-1, 0], [1, 0], [0, -1], [0, 1]];   // up, down, left, right2 3function floodFill(image, sr, sc, color) {4  const original = image[sr][sc];5  if (original === color) return image;            // already that colour: nothing to do6  const rows = image.length, cols = image[0].length;7  const queue = [[sr, sc]];8  image[sr][sc] = color;                           // paint on the way IN: painted means visited9  let head = 0;10  while (head < queue.length) {11    const [r, c] = queue[head++];12    for (const [dr, dc] of DIRS) {13      const nr = r + dr, nc = c + dc;14      if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && image[nr][nc] === original) {15        image[nr][nc] = color;                     // a matching neighbour joins the region16        queue.push([nr, nc]);17      }18    }19  }20  return image;21}

Time O(m · n), space O(m · n). The same work as DFS; the queue holds at most the pixels on the region's moving edge.

Comparing the approaches

Both are correct and equally fast. Use DFS for short code, BFS when the grid can be huge and recursion might overflow.

Edge cases to test

Variations