293. Flood Fill

Recolor the starting pixel and flood outward to 4-connected neighbours that share the original color, stopping at different colors or the border.

DFS flood

Remember the original color of the start pixel. DFS: if the current cell is in bounds and still has the original color, repaint it and recurse into its four neighbours. Guard against an infinite loop when the new color equals the original (return early).

start = image[sr][sc]
if start == color: return image
dfs(r,c): if in bounds and image[r][c]==start: image[r][c]=color; recurse 4 neighbours

Worked example

[[1,1,1],[1,1,0],[1,0,1]], start (1,1), color 2 → the connected region of 1's becomes 2's.

Complexity

• Time: O(m·n).
• Space: O(m·n) recursion.

class Solution {
    private int rows, cols, start, newColor;
    private int[][] image;

    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        this.image = image;
        this.newColor = color;
        start = image[sr][sc];
        if (start == color) return image;
        rows = image.length;
        cols = image[0].length;
        dfs(sr, sc);
        return image;
    }

    private void dfs(int r, int c) {
        if (r < 0 || r >= rows || c < 0 || c >= cols || image[r][c] != start) return;
        image[r][c] = newColor;
        dfs(r + 1, c);
        dfs(r - 1, c);
        dfs(r, c + 1);
        dfs(r, c - 1);
    }
}