733. Flood Fill

/*
BFS Solution

Time Complexity: O(M * N)
Space Complexity: O(M * N) (queue size can grow upto all pixels)

M = Number of rows
N = Number of columns.
*/
class Solution {
    private static final int[][] dirs = new int[][]{{0,1},{1,0},{0,-1},{-1,0}};

    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        if (image == null || image.length == 0 || image[0].length == 0) {
            return new int[0][0];
        }
        int rows = image.length;
        int cols = image[0].length;
        if (sr < 0 || sr >= rows || sc < 0 || sc >= cols || image[sr][sc] == newColor) {
            return image;
        }

        Queue<int[]> queue = new LinkedList();
        int oldColor = image[sr][sc];
        image[sr][sc] = newColor;
        queue.add(new int[]{sr, sc});

        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            for (int[] dir : dirs) {
                int x = cell[0] + dir[0];
                int y = cell[1] + dir[1];
                if (x < 0 || y < 0 || x >= rows || y >= cols || image[x][y] != oldColor) {
                    continue;
                }
                image[x][y] = newColor;
                queue.add(new int[]{x, y});
            }
        }

        return image;
    }
}

/*
DFS Solution

Time Complexity: O(M * N)
Space Complexity: O(M * N) (recursion stack size can grow upto all pixels)

M = Number of rows
N = Number of columns.
*/
class Solution {
    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        if (image == null || image.length == 0 || image[0].length == 0) {
            return new int[0][0];
        }
        if (sr < 0 || sr >= image.length || sc < 0 || sc >= image[0].length || image[sr][sc] == newColor) {
            return image;
        }

        int oldColor = image[sr][sc];
        dfs(image, sr, sc, oldColor, newColor);
        return image;
    }

    private void dfs(int[][] image, int row, int col, int oldColor, int newColor) {
        if (row < 0 || col < 0 || row >= image.length || col >= image[0].length || image[row][col] != oldColor) {
            return;
        }
        image[row][col] = newColor;
        dfs(image, row, col+1, oldColor, newColor);
        dfs(image, row+1, col, oldColor, newColor);
        dfs(image, row, col-1, oldColor, newColor);
        dfs(image, row-1, col, oldColor, newColor);
    }
}