Flood Fill — DFS Color Replace

Problem

Given an m x n image, a starting pixel (sr, sc), and a color, flood fill the image by replacing all pixels of the old color that are 4-connected to start with the new color.

Example:

image = [[1,1,1],[1,1,0],[1,0,1]], sr=1, sc=1, color=2
Output: [[2,2,2],[2,2,0],[2,0,1]]

Approach — DFS with Early Exit

Track the original color. If newColor == oldColor, return immediately (no-op). DFS recurses on matching neighbours.

Time: O(mn) | Space: O(mn)

Solutions

C

void dfs(int** img, int r, int c, int R, int C, int old, int new) {
    if (r<0||r>=R||c<0||c>=C||img[r][c]!=old) return;
    img[r][c]=new;
    dfs(img,r+1,c,R,C,old,new); dfs(img,r-1,c,R,C,old,new);
    dfs(img,r,c+1,R,C,old,new); dfs(img,r,c-1,R,C,old,new);
}
int** floodFill(int** image, int R, int* cols, int sr, int sc, int color, int* outR, int** outCols) {
    int old=image[sr][sc];
    if (old!=color) dfs(image,sr,sc,R,cols[0],old,color);
    *outR=R; *outCols=cols; return image;
}

C++

class Solution {
    void dfs(vector<vector<int>>& img, int r, int c, int old, int col) {
        if (r<0||r>=img.size()||c<0||c>=img[0].size()||img[r][c]!=old) return;
        img[r][c]=col;
        dfs(img,r+1,c,old,col); dfs(img,r-1,c,old,col);
        dfs(img,r,c+1,old,col); dfs(img,r,c-1,old,col);
    }
public:
    vector<vector<int>> floodFill(vector<vector<int>>& img, int sr, int sc, int color) {
        if (img[sr][sc]!=color) dfs(img,sr,sc,img[sr][sc],color);
        return img;
    }
};

Java

class Solution {
    private void dfs(int[][] img, int r, int c, int old, int col) {
        if (r<0||r>=img.length||c<0||c>=img[0].length||img[r][c]!=old) return;
        img[r][c]=col;
        dfs(img,r+1,c,old,col); dfs(img,r-1,c,old,col);
        dfs(img,r,c+1,old,col); dfs(img,r,c-1,old,col);
    }
    public int[][] floodFill(int[][] img, int sr, int sc, int color) {
        if (img[sr][sc]!=color) dfs(img,sr,sc,img[sr][sc],color);
        return img;
    }
}

JavaScript

var floodFill = function(image, sr, sc, color) {
    const old=image[sr][sc];
    if (old===color) return image;
    const dfs=(r,c)=>{
        if(r<0||r>=image.length||c<0||c>=image[0].length||image[r][c]!==old) return;
        image[r][c]=color;
        dfs(r+1,c); dfs(r-1,c); dfs(r,c+1); dfs(r,c-1);
    };
    dfs(sr,sc); return image;
};

Python

class Solution:
    def floodFill(self, image: list[list[int]], sr: int, sc: int, color: int) -> list[list[int]]:
        old = image[sr][sc]
        if old == color: return image
        R, C = len(image), len(image[0])
        def dfs(r, c):
            if not (0<=r<R and 0<=c<C) or image[r][c]!=old: return
            image[r][c]=color
            for dr,dc in [(1,0),(-1,0),(0,1),(0,-1)]:
                dfs(r+dr,c+dc)
        dfs(sr,sc); return image

Complexity

Time: O(mn) | Space: O(mn)

Key Takeaway

Always check old == newColor before starting; skipping this causes infinite recursion.