Skip to content
Shubham JangleResources
Graphs & grids

Explore topics

Flood fill

Watch the walkthrough
Open on Instagram

Problem

Starting at (sr, sc), recolor all four-directionally connected pixels that share the starting pixel's original color.

Approach and revision checks

Changing the pixel before recursion marks it as visited. If old and new colors match, return immediately to avoid repeated recursion. For an r by c grid, worst-case time and recursion stack are O(rc). The source assumes a nonempty rectangular grid and valid coordinates. Large regions may require an iterative stack to avoid a call-stack overflow.

Original repository source

Copied from the supplied local DSA-Series checkout; code and comments are preserved. Run alternative definitions separately when comparing approaches.

12-flood-fill.js

Original file on GitHub

function fill(image, startPixel, i, j, color) {
  if (image[i][j] === startPixel) {
    image[i][j] = color;
    if (i - 1 >= 0) fill(image, startPixel, i - 1, j, color);
    if (j + 1 < image[0].length) fill(image, startPixel, i, j + 1, color);
    if (j - 1 >= 0) fill(image, startPixel, i, j - 1, color);
    if (i + 1 < image.length) fill(image, startPixel, i + 1, j, color);
  }
}

var floodFill = function (image, sr, sc, color) {
  if (image[sr][sc] == color) return image;
  fill(image, image[sr][sc], sr, sc, color);
  return image;
};