Flood fill

Easy TimeO(n·m) SpaceO(n·m)

This is the paint-bucket tool. Given a grid image of colours, a starting cell at sr, sc, and a newColor, the paint spreads to that cell and to every cell reachable from it through neighbours holding the same original colour. Return the repainted grid. Only the four orthogonal neighbours count as connected — diagonals do not — the spread stops at a different colour and at the edge of the grid, and if the starting cell already holds the new colour nothing changes at all.

Examples

Example 1

Input
image = [[1, 1, 1], [1, 1, 0], [1, 0, 1]]sr = 1sc = 1newColor = 2
Output
[[2,2,2],[2,2,0],[2,0,1]]
Six connected 1s become 2s; the 1 in the bottom-right corner touches only diagonally and is left.

Example 2

Input
image = [[1, 1], [1, 1]]sr = 0sc = 0newColor = 1
Output
[[1,1],[1,1]]
The starting cell is already the new colour, so nothing is repainted.

The Code

function floodFill(image, sr, sc, newColor) {
  const startColor = image[sr][sc];
  if (startColor === newColor) return image;
  function fill(r, c) {
    if (r < 0 || r >= image.length || c < 0 || c >= image[0].length) return;
    if (image[r][c] !== startColor) return;
    image[r][c] = newColor;
    fill(r + 1, c);
    fill(r - 1, c);
    fill(r, c + 1);
    fill(r, c - 1);
  }
  fill(sr, sc);
  return image;
}
floodFill([[1, 1, 1], [1, 1, 0], [1, 0, 1]], 1, 1, 2);
Done
Step through floodFill([[1, 1, 1], [1, 1, 0], [1, 0, 1]], 1, 1, 2) call by call

More like this

All matrices & grids examples (7) →