Flood Fill: Depth First Search*

First Thoughs: intution was leaning towards dfs, recursive solution. As the starting point is given, and similar actions need to be done for adjacent pixels. Implemented recursive solution. Had a very close solution, but main problem was 1. recursive solutions generally do not require a while loop. they function well without one, need to review concept of recursion further 2. always only think about handling the one case in hand. in this case, the pixel, if color equals to original color, should change.

My Solution: faulty, but close -> remember, recursive solutions/bfs generally should not resemble this

class Solution {
    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        //up: [sr-1][sc], down: [sr+1][sc], left: [sr][sc-1], right: [sr][sc+1]
        //perhaps call void return function multiple times
        if (sr<0 || sc<0) return image;
        doFlood(image, sr, sc, newColor, image[sr][sc]);
        return image;
    }
    public void doFlood(int[][] image, int sr, int sc, int newColor, int original) {
        //check all four adjacents, and if equal to pixel color, set to new color
        while (sr<image.length && sc<image[0].length) {
            if ((sr-1)>=0 && sc>=0 && image[sr-1][sc]==original) {
            image[sr-1][sc] = newColor;
            doFlood(image, sr-1, sc, newColor, original);
        }
        if (sr+1>=0 && sc>= 0 && image[sr+1][sc]==original) {
            image[sr+1][sc] = newColor;
            doFlood(image, sr+1, sc, newColor, original);
        }
        if (sr>=0 && sc-1>=0 && image[sr][sc-1]==original) {
            image[sr][sc-1] = newColor;
            doFlood(image, sr, sc-1, newColor, original);
        }
        if (sr>=0 && sc+1>=0 && image[sr][sc+1]==original) {
            image[sr][sc+1] = newColor;
            doFlood(image, sr, sc+1, newColor, original);
        }
        }
        
    }
}

Correct BFS Solution:

class Solution {
    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        if (image[sr][sc]!=newColor) doFlood(image, sr, sc, newColor, image[sr][sc]);
        return image;
    }
    public void doFlood(int[][] image, int sr, int sc, int newColor, int original) {
        //if equal to original color, set to new color, call on its adjacents
        image[sr][sc] = newColor;
        if (sr-1>=0 && sc>=0 && image[sr-1][sc]==original)
        doFlood(image, sr-1, sc, newColor, original);
        if (sr+1<image.length && sc>=0 && image[sr+1][sc]==original)
        doFlood(image, sr+1, sc, newColor, original);
        if (sr>=0 && sc-1>=0 && image[sr][sc-1]==original)
        doFlood(image, sr, sc-1, newColor, original);
        if (sr>=0 && sc+1<image[0].length && image[sr][sc+1]==original)
        doFlood(image, sr, sc+1, newColor, original);
        
    }
}

This solution can also be simplified into removing zero checkers and reorganizing code so that condition of comparing current color to original color is done once at the start of doFlood(), rather than checking every time, but just some optional things. In other words, check once at the start of doFlood as conditional statement.

Catch Point:

1. Recursive solutions are inherently 'recursive' in that they don't require a while loop to execute the function multiple times.
2. The fact that the array is pass by reference is what allows the void method to edit the array, which is returned at the desired modified state.
3. The conditional statement, checking if the starting pixel is not the new Color, is essential -> not checking this will result in stack overflow error!
4. row-1 has the possibility of getting negative index but row+1 has the danger of passing over the array length -> leading to different conditions to check! not always checking whether they are positive