Flood Fill

An image is represented by a 2-D array of integers, each integer representing the pixel value of the image (from 0 to 65535).

Given a coordinate (sr, sc) representing the starting pixel (row and column) of the flood fill, and a pixel value newColor, "flood fill" the image.

To perform a "flood fill", consider the starting pixel, plus any pixels connected 4-directionally to the starting pixel of the same color as the starting pixel, plus any pixels connected 4-directionally to those pixels (also with the same color as the starting pixel), and so on. Replace the color of all of the aforementioned pixels with the newColor.

At the end, return the modified image.

Input: 
image = [[1,1,1],[1,1,0],[1,0,1]]
sr = 1, sc = 1, newColor = 2
Output: [[2,2,2],[2,2,0],[2,0,1]]
Explanation: 
From the center of the image (with position (sr, sc) = (1, 1)), all pixels connected 
by a path of the same color as the starting pixel are colored with the new color.
Note the bottom corner is not colored 2, because it is not 4-directionally connected
to the starting pixel.

Note:

• The length of image and image[0] will be in the range [1, 50].
• The given starting pixel will satisfy 0 <= sr < image.length and 0 <= sc < image[0].length.
• The value of each color in image[i][j] and newColor will be an integer in [0, 65535].

---

Now, let analyze the problem with the above input example and using its explanation. We will convert the image input to the 2D matrix.

1	1	1
1	1	0
1	0	1

We have sr which represents the row in a matrix and sc which represents the column in a matrix. We have to see in the above index row 1 and column 1 which is a middle element of the matrix. We have to change all the elements that are immediate neighbors to middle and their element value is the same as the middle element value, it will call recursively till all the neighbor's neighbor will change with a newColor value.

Note if the value of the matrix[row][column] index is the same as newColor then return the same matrix without doing any changes.

Step 1:- Find the value of the given row and column and change it. In this case, newColor value is 2 and the existing value of the particular matrix[row][column] index is 1, will change it.

1	1	1
1	2	0
1	0	1

Step 2:-We have to call 4 different recursive calls (Top, Left, bottom, right) and do the update the value until we reach base condition and terminate the recursion.

1	2	1
2	2	0
1	0	1

2	2	2
2	2	0
1	0	1

2	2	2
2	2	0
2	0	1

It is more like updating the neighbor's value recursively until the base condition will be true. We have already learned about recursion where we have to specify a base condition where our loop will going to be terminated. In this scenario we have to check if the row or column is out of bound and matrix value of row and column is not the same as the initial value.

Let's do the code and understand it in deep dive.

    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        if (image == null || image.length == 0 || image[sr][sc] == newColor)
            return image;
        fill(image, sr, sc, image[sr][sc], newColor);
        return image;
    }

    private void fill(int[][] image, int row, 
                        int column, int initialValue, int newValue) {
//        It checks row isn't in between 0 to length,
//        column isn't also in between 0 to length,
//        image particular row and column is not same as initialValue
        if (row < 0 || row >= image.length || column < 0 ||
             column >= image[0].length || image[row][column] != initialValue)
            return;
//        Check if matches then update the value.
        if (image[row][column] == initialValue)
            image[row][column] = newValue;
//        Top row recursive call
        fill(image, row-1, column, initialValue, newValue);
//        Bottom row recursive call
        fill(image, row+1, column, initialValue, newValue);
//        Left column recursive call
        fill(image, row, column-1, initialValue, newValue);
//        right column recursive call
        fill(image, row, column+1, initialValue, newValue);
    }