Menu

Earn Premium with Referrals

Invite your friends and earn Premium rewards through our referral program.

See how it works and start inviting friends.

Flood Fill
DSA

Flood Fill

Understand flood fill using DFS or BFS to process connected regions in a matrix.

Flood Fill processes the connected region of same-valued cells starting from one cell.

Focus on recognizing:

“Paint bucket” / “expand region” / “count islands” → DFS or BFS over 4 directions

Pattern 1: DFS Flood Fill

Watch BFS recolor the connected 1s from (1,1) — the isolated cells stay untouched. Press ▶ to animate.

Flood Fill (BFS)

Flood fill recolors a connected region of the same value, starting from a seed cell, using BFS. Each popped cell recolors itself and enqueues its same-colored 4-neighbors.

Grid: [[1,1,1],[1,1,0],[1,0,1]]. Seed (1,1), new color 2. BFS spreads outward layer by layer — watch the 1s flip to 2s. The 0s are a different value, so they are never recolored.

GRID VISUALIZER
Steps –
1
1
1
1
1
0
1
0
1
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        queue = [(sr, sc)]; color it; mark visited
                      
                        2
                        while queue not empty:
                      
                        3
                          pop (r, c)
                      
                        4
                          for each of 4 neighbors:
                      
                        5
                            if in bounds && same old color: color + enqueue
                      
public int[][] floodFill(int[][] image, int sr, int sc, int color) {
    int original = image[sr][sc];

    if (original != color) {          // avoid infinite loop
        dfs(image, sr, sc, original, color);
    }

    return image;
}

private void dfs(int[][] grid, int row, int col,
                 int original, int newColor) {
    int n = grid.length, m = grid[0].length;

    if (row < 0 || row >= n || col < 0 || col >= m) return;
    if (grid[row][col] != original) return;

    grid[row][col] = newColor;        // mark visited

    dfs(grid, row + 1, col, original, newColor);
    dfs(grid, row - 1, col, original, newColor);
    dfs(grid, row, col + 1, original, newColor);
    dfs(grid, row, col - 1, original, newColor);
}
def flood_fill(image, sr, sc, color):
    original = image[sr][sc]

    if original == color:             # avoid infinite loop
        return image

    rows, cols = len(image), len(image[0])

    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return
        if image[r][c] != original:
            return

        image[r][c] = color           # mark visited

        dfs(r + 1, c)
        dfs(r - 1, c)
        dfs(r, c + 1)
        dfs(r, c - 1)

    dfs(sr, sc)
    return image
void dfs(vector<vector<int>>& grid, int row, int col,
         int original, int newColor) {
    int n = grid.size(), m = grid[0].size();

    if (row < 0 || row >= n || col < 0 || col >= m) return;
    if (grid[row][col] != original) return;

    grid[row][col] = newColor;        // mark visited

    dfs(grid, row + 1, col, original, newColor);
    dfs(grid, row - 1, col, original, newColor);
    dfs(grid, row, col + 1, original, newColor);
    dfs(grid, row, col - 1, original, newColor);
}

vector<vector<int>> floodFill(vector<vector<int>>& image,
                              int sr, int sc, int color) {
    int original = image[sr][sc];

    if (original != color)
        dfs(image, sr, sc, original, color);

    return image;
}
function floodFill(image, sr, sc, color) {
  const original = image[sr][sc];

  if (original === color) return image; // avoid infinite loop

  const rows = image.length,
    cols = image[0].length;

  const dfs = (r, c) => {
    if (r < 0 || r >= rows || c < 0 || c >= cols) return;
    if (image[r][c] !== original) return;

    image[r][c] = color; // mark visited

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

  dfs(sr, sc);
  return image;
}

The original == color early-exit prevents infinite recursion when the new color equals the old.

Bounds check → value check → mark → recurse/queue. Same skeleton for both traversals.

Pattern 2: BFS Flood Fill

Same logic with an explicit queue (no recursion depth risk):

public int[][] floodFill(int[][] image, int sr, int sc, int color) {
    int original = image[sr][sc];

    if (original == color) return image;

    int rows = image.length, cols = image[0].length;
    Queue<int[]> queue = new LinkedList<>();
    queue.offer(new int[]{sr, sc});
    image[sr][sc] = color;

    while (!queue.isEmpty()) {
        int[] cell = queue.poll();
        int r = cell[0], c = cell[1];

        int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};

        for (int[] d : dirs) {
            int nr = r + d[0], nc = c + d[1];

            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
                    && image[nr][nc] == original) {
                image[nr][nc] = color;
                queue.offer(new int[]{nr, nc});
            }
        }
    }

    return image;
}
from collections import deque

def flood_fill(image, sr, sc, color):
    original = image[sr][sc]

    if original == color:
        return image

    rows, cols = len(image), len(image[0])
    queue = deque([(sr, sc)])
    image[sr][sc] = color

    while queue:
        r, c = queue.popleft()

        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc

            if 0 <= nr < rows and 0 <= nc < cols \
                    and image[nr][nc] == original:
                image[nr][nc] = color
                queue.append((nr, nc))

    return image
vector<vector<int>> floodFill(vector<vector<int>>& image,
                              int sr, int sc, int color) {
    int original = image[sr][sc];

    if (original == color) return image;

    int rows = image.size(), cols = image[0].size();
    queue<pair<int, int>> q;
    q.push({sr, sc});
    image[sr][sc] = color;

    int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    while (!q.empty()) {
        auto [r, c] = q.front();
        q.pop();

        for (auto& d : dirs) {
            int nr = r + d[0], nc = c + d[1];

            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
                    && image[nr][nc] == original) {
                image[nr][nc] = color;
                q.push({nr, nc});
            }
        }
    }

    return image;
}
function floodFill(image, sr, sc, color) {
  const original = image[sr][sc];

  if (original === color) return image;

  const rows = image.length,
    cols = image[0].length;
  const queue = [[sr, sc]];
  image[sr][sc] = color;

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

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

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

      if (
        nr >= 0 &&
        nr < rows &&
        nc >= 0 &&
        nc < cols &&
        image[nr][nc] === original
      ) {
        image[nr][nc] = color;
        queue.push([nr, nc]);
      }
    }
  }

  return image;
}

Pattern 3: Connected Components (Count Islands)

Scan every cell; each unvisited land cell starts a fill that consumes its whole component:

public int countComponents(int[][] grid) {
    int count = 0;

    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[0].length; j++) {

            if (grid[i][j] == 1) {
                count++;
                sink(grid, i, j);     // consume component
            }
        }
    }

    return count;
}

private void sink(int[][] grid, int row, int col) {
    if (row < 0 || row >= grid.length
            || col < 0 || col >= grid[0].length
            || grid[row][col] != 1) {
        return;
    }

    grid[row][col] = 0;               // mark visited

    sink(grid, row + 1, col);
    sink(grid, row - 1, col);
    sink(grid, row, col + 1);
    sink(grid, row, col - 1);
}
def count_components(grid):
    rows, cols = len(grid), len(grid[0])

    def sink(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != 1:
            return

        grid[r][c] = 0                # mark visited

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

    count = 0

    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == 1:
                count += 1
                sink(i, j)

    return count
void sink(vector<vector<int>>& grid, int row, int col) {
    if (row < 0 || row >= (int)grid.size()
            || col < 0 || col >= (int)grid[0].size()
            || grid[row][col] != 1) {
        return;
    }

    grid[row][col] = 0;               // mark visited

    sink(grid, row + 1, col);
    sink(grid, row - 1, col);
    sink(grid, row, col + 1);
    sink(grid, row, col - 1);
}

int countComponents(vector<vector<int>>& grid) {
    int count = 0;

    for (int i = 0; i < (int)grid.size(); i++)
        for (int j = 0; j < (int)grid[0].size(); j++)
            if (grid[i][j] == 1) {
                count++;
                sink(grid, i, j);
            }

    return count;
}
function countComponents(grid) {
  const rows = grid.length,
    cols = grid[0].length;

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

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

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

  let count = 0;

  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      if (grid[i][j] === 1) {
        count++;
        sink(i, j);
      }
    }
  }

  return count;
}

Marking visited by writing 0 into the grid avoids a separate visited set — mutate only when mutation is allowed.

Common Mistakes

Missing the original == color guard.

Recoloring a cell to its own color makes DFS revisit it forever.

Forgetting bounds checks.

Every recursive call / neighbor access needs 0 <= nr < rows && 0 <= nc < cols.

Deep recursion on huge grids.

A 300×300 all-land grid can overflow the stack in Java/JS — switch to BFS or an explicit stack.

Complexity

OperationTimeSpace
Flood fillO(n·m)O(n·m) recursion/queue worst case
ComponentsO(n·m)O(n·m) worst

My Private Notes

Notes are auto-saved locally to this device.