Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Easygraph-dfs

Flood Fill

Problem (restated)

Given an image grid, a start cell (sr, sc), and a new color, recolor the connected 4-direction component that contains the start (cells equal to the original color) and return the image.

Intuition

The start cell seeds one component. Visit every 4-neighbor that still has the original color and paint it. If the new color equals the original, return immediately or you recurse forever.

Approaches

Recursive DFS fill

Unverified

Time O(m·n)Space O(m·n) worst-case stack

Idea. orig = image[sr][sc]. If orig === color, return. DFS: out of bounds or not orig → stop; else paint and recurse in four directions.

Walkthrough. [[1,1,1],[1,1,0],[1,0,1]], start (1,1), color 2 → the four connected 1s become 2; the corner 1 is diagonal-only so it stays.

Trade-offs. Shortest code. Recursion depth is the component size; huge fills can blow the stack.

Solution

export function floodFill(
  image: number[][],
  sr: number,
  sc: number,
  color: number,
): number[][] {
  const orig = image[sr]![sc]!;
  if (orig === color) return image;
  const m = image.length, n = image[0]!.length;
  const dfs = (r: number, c: number) => {
    if (r < 0 || c < 0 || r >= m || c >= n || image[r]![c] !== orig) return;
    image[r]![c] = color;
    dfs(r + 1, c); dfs(r - 1, c); dfs(r, c + 1); dfs(r, c - 1);
  };
  dfs(sr, sc);
  return image;
}

export function floodFill(
  image: number[][],
  sr: number,
  sc: number,
  color: number,
): number[][] {
  const orig = image[sr]![sc]!;
  if (orig === color) return image;
  const m = image.length, n = image[0]!.length;
  const dfs = (r: number, c: number) => {
    if (r < 0 || c < 0 || r >= m || c >= n || image[r]![c] !== orig) return;
    image[r]![c] = color;
    dfs(r + 1, c); dfs(r - 1, c); dfs(r, c + 1); dfs(r, c - 1);
  };
  dfs(sr, sc);
  return image;
}

Iterative stack fill

Unverified

Time O(m·n)Space O(m·n)

Idea. Same paint rule, explicit stack. Pop a cell, skip if not orig, paint, push four neighbors.

Walkthrough. Same grid, same result. The stack is the pending frontier of the component.

Trade-offs. Matches the graph-DFS template and avoids call-stack limits. BFS with a queue is the same idea if you need level order (you do not, here).

Solution

export function floodFill(
  image: number[][],
  sr: number,
  sc: number,
  color: number,
): number[][] {
  const orig = image[sr]![sc]!;
  if (orig === color) return image;
  const m = image.length, n = image[0]!.length;
  const stack: [number, number][] = [[sr, sc]];
  while (stack.length) {
    const [r, c] = stack.pop()!;
    if (r < 0 || c < 0 || r >= m || c >= n || image[r]![c] !== orig) continue;
    image[r]![c] = color;
    stack.push([r + 1, c], [r - 1, c], [r, c + 1], [r, c - 1]);
  }
  return image;
}

export function floodFill(
  image: number[][],
  sr: number,
  sc: number,
  color: number,
): number[][] {
  const orig = image[sr]![sc]!;
  if (orig === color) return image;
  const m = image.length, n = image[0]!.length;
  const stack: [number, number][] = [[sr, sc]];
  while (stack.length) {
    const [r, c] = stack.pop()!;
    if (r < 0 || c < 0 || r >= m || c >= n || image[r]![c] !== orig) continue;
    image[r]![c] = color;
    stack.push([r + 1, c], [r - 1, c], [r, c + 1], [r, c - 1]);
  }
  return image;
}

Template connection

Flood-fill shape of Graph DFS: mutate the cell, then DFS/stack the 4-neighbors. LC 695 is the same walk, returning an area instead of painting a color.

Reflection

If the starting color is already the target color, return the image unchanged. Otherwise paint every 4-connected cell of the original color.
Painting is the visited mark. Painting a cell with the color it already has never stops; the early return is what cuts that loop.
DFS and an explicit stack paint the same region. One cell is enough. Stay inside the image.