Flood Fill

You're given an image as a 2D grid of integers image, where each value is a pixel's color. You're also given a starting pixel (sr, sc) and a new color.

Perform a "paint bucket" fill: the starting pixel, and every pixel connected to it through a chain of up, down, left or right neighbors that all share the starting pixel's original color, should be changed to color. Diagonal neighbors do not count as connected.

Return the image after the fill.

The grid is a graph: each pixel is a node, and it has an edge to each of its four neighbors that share its color. The fill is "find the connected component containing the start and recolor it", which is exactly what a depth-first or breadth-first search does.

You don't even need a separate visited set. Recoloring a pixel as soon as you reach it marks it as done, since it no longer has the original color and the search won't enter it again.

That trick has one hole: if color equals the original color, recoloring changes nothing, so every pixel still looks unvisited and the search loops forever. Check for that case first and return the image unchanged.

def flood_fill(image: list[list[int]], sr: int, sc: int, color: int) -> list[list[int]]:
    old = image[sr][sc]
    if old == color:
        return image  # nothing to change, and recoloring would not mark visits
    rows, cols = len(image), len(image[0])
    image[sr][sc] = color
    stack = [(sr, sc)]
    while stack:
        r, c = stack.pop()
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if 0 <= nr < rows and 0 <= nc < cols and image[nr][nc] == old:
                image[nr][nc] = color
                stack.append((nr, nc))
    return image

function floodFill(image, sr, sc, color) {
  const old = image[sr][sc];
  if (old === color) return image; // nothing to change, and recoloring would not mark visits
  const rows = image.length;
  const cols = image[0].length;
  image[sr][sc] = color;
  const stack = [[sr, sc]];
  while (stack.length) {
    const [r, c] = stack.pop();
    for (const [nr, nc] of [[r + 1, c], [r - 1, c], [r, c + 1], [r, c - 1]]) {
      if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && image[nr][nc] === old) {
        image[nr][nc] = color;
        stack.push([nr, nc]);
      }
    }
  }
  return image;
}

Name the graph view in one line: "pixels are nodes, same-colored neighbors are edges, and I'm recoloring one connected component." Then mention the same-color edge case before you write any code; interviewers often wait to see whether you catch it.

Say why you don't need a visited set (recoloring marks pixels), and mention the recursion depth if you write the recursive version. Offering the explicit stack as the safe alternative is usually enough.