Flood Fill

Introduction and Purpose

Flood fill is an algorithm that spreads outward from a starting cell in a grid, visiting every connected cell that shares a given property — and doing something to each one. You use it every time you click the paint bucket tool in an image editor: click a region, and all connected pixels of the same color get repainted at once.

The algorithm has two moving parts: a rule for which cells to visit (same color, same type, not yet visited), and a direction model for what counts as "connected" (up/down/left/right, or also diagonals). Everything else is just graph traversal applied to a grid.

Problems Addressed

Any problem that asks "given a starting point, how far can I reach?" maps to flood fill. The grid can represent pixels, rooms, land tiles, network nodes, or any cell-based structure.

4-directional vs 8-directional connectivity

The most important design decision is: what counts as a neighbor?

4-connectivity (orthogonal): up, down, left, right. Used when diagonal movement is not allowed — like most grid-based path problems and the standard flood fill in image editors.

8-connectivity (includes diagonals): all eight surrounding cells. Used when diagonal connections matter — like counting islands where land diagonally touching is still considered connected.

Common Approaches

Approach 1: Recursive DFS

The most natural way to write flood fill. From the current cell, recursively fill each valid neighbor. The call stack manages the traversal order automatically.

function floodFillRecursive(image, sr, sc, newColor) {
  const originalColor = image[sr][sc];

  // No-op if the starting cell is already the new color
  if (originalColor === newColor) return image;

  function dfs(r, c) {
    // Out of bounds or wrong color — stop
    if (r < 0 || r >= image.length) return;
    if (c < 0 || c >= image[0].length) return;
    if (image[r][c] !== originalColor) return;

    image[r][c] = newColor; // Paint this cell

    dfs(r - 1, c); // Up
    dfs(r + 1, c); // Down
    dfs(r, c - 1); // Left
    dfs(r, c + 1); // Right
  }

  dfs(sr, sc);
  return image;
}

// Example: paint bucket at (1,1), changing 1s to 2
const image = [
  [1, 1, 1],
  [1, 1, 0],
  [1, 0, 0],
];
console.log(floodFillRecursive(image, 1, 1, 2));
// [[2,2,2],[2,2,0],[2,0,0]]

Time: O(m × n) — each cell is visited at most once.
Space: O(m × n) — the recursion depth in the worst case (a fully connected grid).

When to be careful: Deep recursion on large grids can hit JavaScript's call stack limit. A 1000×1000 fully connected grid means up to 1,000,000 recursive calls — that will overflow. For large grids, use the iterative approach below.

---

Approach 2: Iterative BFS (queue)

Replace the call stack with an explicit queue. Cells are visited in waves radiating outward from the start — like ripples in water. This avoids stack overflow and makes the fill order predictable.

function floodFillBFS(image, sr, sc, newColor) {
  const originalColor = image[sr][sc];
  if (originalColor === newColor) return image;

  const rows = image.length;
  const cols = image[0].length;
  const queue = [[sr, sc]];
  image[sr][sc] = newColor; // Paint immediately when enqueuing

  const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];

  while (queue.length > 0) {
    const [r, c] = queue.shift();

    for (const [dr, dc] of directions) {
      const nr = r + dr;
      const nc = c + dc;

      if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && image[nr][nc] === originalColor) {
        image[nr][nc] = newColor; // Paint before enqueuing to avoid duplicates
        queue.push([nr, nc]);
      }
    }
  }

  return image;
}

Note: paint the cell when you enqueue it, not when you dequeue it. Painting on dequeue lets the same cell get enqueued multiple times before it's processed, wasting work. Painting on enqueue marks it immediately.

---

Approach 3: Iterative DFS (stack)

Same as BFS but uses a stack (LIFO) instead of a queue (FIFO). Fill order is depth-first — it digs deep into one path before backtracking. In practice, DFS and BFS produce the same final result for flood fill; the difference is only the order cells are painted.

function floodFillDFS(image, sr, sc, newColor) {
  const originalColor = image[sr][sc];
  if (originalColor === newColor) return image;

  const rows = image.length;
  const cols = image[0].length;
  const stack = [[sr, sc]];
  image[sr][sc] = newColor;

  const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];

  while (stack.length > 0) {
    const [r, c] = stack.pop(); // Stack: last in, first out

    for (const [dr, dc] of directions) {
      const nr = r + dr;
      const nc = c + dc;

      if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && image[nr][nc] === originalColor) {
        image[nr][nc] = newColor;
        stack.push([nr, nc]);
      }
    }
  }

  return image;
}

For flood fill specifically, prefer BFS when you care about fill order (e.g., shortest path to each cell) and iterative DFS when you just need any correct fill without recursion overhead.

---

Real-world example: counting islands

One of the most common interview problems is built on flood fill: given a grid of '1' (land) and '0' (water), count the number of islands (groups of connected land cells).

The approach: scan every cell. When you find an unvisited land cell, that's a new island — increment the count, then flood-fill the entire island to mark it as visited so it isn't counted again.

function numIslands(grid) {
  const rows = grid.length;
  const cols = grid[0].length;
  let count = 0;

  function sink(r, c) {
    // Out of bounds or water or already visited — stop
    if (r < 0 || r >= rows || c < 0 || c >= cols) return;
    if (grid[r][c] !== '1') return;

    grid[r][c] = '0'; // Mark as visited by "sinking" the land

    sink(r - 1, c);
    sink(r + 1, c);
    sink(r, c - 1);
    sink(r, c + 1);
  }

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === '1') {
        count++;     // Found a new island
        sink(r, c);  // Erase the whole island so we don't count it again
      }
    }
  }

  return count;
}

const grid = [
  ['1','1','0','0','0'],
  ['1','1','0','0','0'],
  ['0','0','1','0','0'],
  ['0','0','0','1','1'],
];
console.log(numIslands(grid)); // 3

The "sink" trick (overwriting visited cells to a sentinel value) avoids needing a separate visited array. It works when you're allowed to modify the input. If the grid must stay intact, keep a visited boolean array of the same dimensions instead.

---

Real-world example: finding the largest connected region

A natural extension — not just counting regions but measuring them:

function maxAreaOfIsland(grid) {
  const rows = grid.length;
  const cols = grid[0].length;

  function fill(r, c) {
    if (r < 0 || r >= rows || c < 0 || c >= cols) return 0;
    if (grid[r][c] !== 1) return 0;

    grid[r][c] = 0; // Mark visited

    return 1 + fill(r - 1, c) + fill(r + 1, c) + fill(r, c - 1) + fill(r, c + 1);
  }

  let maxArea = 0;
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === 1) {
        maxArea = Math.max(maxArea, fill(r, c));
      }
    }
  }

  return maxArea;
}

const grid = [
  [0,0,1,0,0,0,0,1,0,0,0,0,0],
  [0,0,0,0,0,0,0,1,1,1,0,0,0],
  [0,1,1,0,1,0,0,0,0,0,0,0,0],
  [0,1,0,0,1,1,0,0,1,0,1,0,0],
  [0,1,0,0,1,1,0,0,1,1,1,0,0],
  [0,0,0,0,0,0,0,0,0,0,1,0,0],
  [0,0,0,0,0,0,0,1,1,1,0,0,0],
  [0,0,0,0,0,0,0,1,1,0,0,0,0],
];
console.log(maxAreaOfIsland(grid)); // 6

Choosing the Right Variant

Related Algorithms and Data Structures

Flood fill is essentially graph traversal applied to a grid. Understanding the underlying graph algorithms unlocks a much wider problem space.

• Depth-First Search (DFS): The recursive flood fill is exactly DFS applied to a grid. Learning DFS on graphs generalizes flood fill to arbitrary structures — trees, social networks, dependency graphs. Search for "DFS graph algorithm" for the general form.
• Breadth-First Search (BFS): The queue-based flood fill is exactly BFS. BFS has the extra property that it visits cells in order of distance from the start, making it the go-to for shortest-path problems on unweighted grids.
• Connected Components: Flood fill is the standard way to find connected components — groups of cells/nodes that can reach each other. Running flood fill once per unvisited cell labels every component.
• Union-Find (Disjoint Set Union): An alternative data structure for answering "are these two cells connected?" efficiently on static grids. Better when you have many point queries; flood fill is better when you need to process whole regions.

Tests and Challenges

Difficulty	Problem	Platform	What it tests
Easy	Flood Fill	LeetCode #733	Pure flood fill, canonical
Easy	Connected Cell in a Grid	HackerRank	Max island size, 8-connectivity
Medium	Number of Islands	LeetCode #200	Count connected components
Medium	Max Area of Island	LeetCode #695	Measure regions
Medium	Surrounded Regions	LeetCode #130	Fill from borders inward
Medium	Rotting Oranges	LeetCode #994	Multi-source BFS flood fill
Medium	Pacific Atlantic Water Flow	LeetCode #417	Two flood fills, find intersection
Hard	Shortest Path in Binary Matrix	LeetCode #1091	BFS flood fill with distance tracking

Start with LeetCode #733 — it's the direct implementation problem. Then do #200 to see how flood fill becomes a building block. #994 (Rotting Oranges) introduces multi-source BFS, where you start the flood from multiple cells simultaneously — a common interview pattern.

Related Concepts

• Binary Search — The "search on the answer" pattern (Approach 4 in the Binary Search article) is often combined with BFS flood fill: binary search on a threshold value, then use a flood fill to check whether the target is reachable under that constraint.
• Dynamic Programming — Some grid problems combine flood fill for connectivity with DP for optimization (e.g., longest path in a grid).
• Big O Notation — Flood fill is O(m × n) in both time and space; understanding why helps when reasoning about large-grid performance.