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