DEV Community

ZeeshanAli-0704
ZeeshanAli-0704

Posted on

Flood Fill - using Recursion - Backtracking

Solution 1 - Keeping track of row & column indices to avoid undefined case

var floodFill = function(image, sr, sc, color) {
    const fill = (i, j, val) => {
        image[i][j] = color;
        if (i > 0 && val == image[i - 1][j]) fill(i - 1, j, val);
        if (j > 0 && val == image[i][j - 1]) fill(i, j - 1, val);
        if (i < image.length - 1  && val == image[i + 1][j]) fill(i + 1, j, val);
        if (j < image[0].length - 1 && val == image[i][j + 1]) fill(i, j + 1, val);
    }
    if (image[sr][sc] == color) return image;
    fill(sr, sc, image[sr][sc]);
    return image;
};
Enter fullscreen mode Exit fullscreen mode

Solution 2 - Not Keeping track of rows & column but handling undefined condition

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

  if (startingColor === color) return image;

  return fillColor(image, sr, sc, color, startingColor);
};

const fillColor = (image, sr, sc, color, startingColor) => {
  if (image?.[sr]?.[sc] === undefined || image[sr][sc] !== startingColor) {
    return image;
  }


  if (image[sr][sc] === color) {
    return image;
  }

  image[sr][sc] = color;
  fillColor(image, sr, sc - 1, color, startingColor);
  fillColor(image, sr + 1, sc, color,  startingColor);
  fillColor(image, sr, sc + 1, color, startingColor);
  fillColor(image, sr - 1, sc, color, startingColor);


  return image;
};
Enter fullscreen mode Exit fullscreen mode

Top comments (0)