Flood fill
Watch the walkthrough
Open on InstagramProblem
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
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;
};