The problem involves performing a flood fill operation on an image represented as a 2D
grid using Depth-First Search (DFS)
traversal. We start from a given
pixel(sr, sc) and
change its color to the
newColor. We then recursively apply the
same operation to all
adjacent pixels(up,
down, left, right) that have the same color as the starting pixel. We need to ensure that we
handle edge cases, such
as
going out of bounds or when the new
color is the same as the old color, to avoid infinite recursion.
class Solution { public void dfs(int[][] image, int sr, int sc, int oldColor,int newColor){ if(sr>=image.length || sr<0 || sc>=image[0].length || sc<0 || image[sr][sc]!=oldColor || image[sr][sc]==newColor) return; // Color the pixel and try to traverse in all 4 directions. image[sr][sc] = newColor; dfs(image,sr+1,sc,oldColor,newColor); dfs(image,sr-1,sc,oldColor,newColor); dfs(image,sr,sc+1,oldColor,newColor); dfs(image,sr,sc-1,oldColor,newColor); } public int[][] floodFill(int[][] image, int sr, int sc, int newColor) { int oldColor = image[sr][sc]; dfs(image,sr,sc,oldColor,newColor); return image; } }
The algorithm visits each pixel in the image once, making it linear in time complexity, where
'n' is the total
number of pixels in the image.
The space complexity is determined by the depth of the recursion stack, which can go up to 'h', where 'h' is the
height of the recursion tree. In the worst case, it can be O(n) if
the image is
filled with the same color.