733. Flood Fill

Recursive approach

var dfs = function (image, r, c, color, newColor) {
  if (image[r][c] == color) {
    image[r][c] = newColor;
    if (r >= 1) dfs(image, r - 1, c, color, newColor);
    if (c >= 1) dfs(image, r, c - 1, color, newColor);
    if (r + 1 < image.length) dfs(image, r + 1, c, color, newColor);
    if (r + 1 < image[0].length) dfs(image, r, c + 1, color, newColor);
  }
};

/**
 * @param {number[][]} image
 * @param {number} sr
 * @param {number} sc
 * @param {number} color
 * @return {number[][]}
 */
var floodFill = function (image, sr, sc, color) {
  const currColor = image[sr][sc];
  if (currColor != color) {
    dfs(image, sr, sc, currColor, color);
  }
  return image;
};

Complexity

  • Time Complexity: O(N), where N is the number of pixels in the image. We might process every pixel.
  • Space Complexity: O(N), the size of the implicit call stack when calling dfs().

All Solutions