733 Flood Fill

Techniques

• Graph
• Simple DFS

Approach:

• If the current pixel already has the newColor, return the image as it is.
• Call the utility dfs function (defined below) for our starting point. ( image[sr][sc] )
• Pixels grid will get modified accordingly, and can be returned.
• In the dfs function
  • check for the boundary conditions, and check if that pixel at image[row][col] equals oldColor (color of the starting pixel) and do return accordingly.
  • Change the pixel value to newColor
  • Call the dfs recursively on the 4-directionally neighbouring pixels of the current pixel.

Complexity

• Time Complexity: O(mn) in the worst case, we will have to visit all pixels.
• Space Complexity: O(1)

Code:

class Solution {
    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {



        if(image[sr][sc] == newColor) return image;

        int m = image.length;
        int n = image[0].length;

        dfs(image, sr, sc, image[sr][sc], newColor);

        return image;
    }

    static void dfs(int[][] image, int row, int col, int oldColor, int newColor){


        if(row < 0 || row >= image.length ||  col < 0 || col >=  image[0].length  || image[row][col] != oldColor) return;


        image[row][col] = newColor;

        dfs(image, row - 1, col, oldColor, newColor);
        dfs(image, row + 1, col, oldColor, newColor);
        dfs(image, row, col - 1, oldColor, newColor);
        dfs(image, row, col + 1, oldColor, newColor);

        return;


    }


}