← Recursion

Flood Fill

Medium
Python
def flood_fill(image,sr,sc,color):
    orig=image[sr][sc]
    if orig==color: return image
    def fill(r,c):
        if 0<=r<len(image) and 0<=c<len(image[0]) and image[r][c]==orig:
            image[r][c]=color
            fill(r+1,c);fill(r-1,c);fill(r,c+1);fill(r,c-1)
    fill(sr,sc)
    return image
Java
public int[][] floodFill(int[][] img,int sr,int sc,int color){
    int orig=img[sr][sc];
    if(orig==color) return img;
    fill(img,sr,sc,orig,color);
    return img;
}
void fill(int[][] img,int r,int c,int orig,int color){
    if(r<0||r>=img.length||c<0||c>=img[0].length||img[r][c]!=orig) return;
    img[r][c]=color;
    fill(img,r+1,c,orig,color);fill(img,r-1,c,orig,color);
    fill(img,r,c+1,orig,color);fill(img,r,c-1,orig,color);
}

Key Insight

Python nested function captures orig/color. Java passes them explicitly.

Python → Java Differences

  • Nested function captures orig/color
  • Java passes all as parameters
  • 4-direction DFS identical
Python
def flood_fill(image,sr,sc,color):
    orig=image[sr][sc]
    if orig==color: return image
    def fill(r,c):
        if 0<=r<len(image) and 0<=c<len(image[0]) and image[r][c]==orig:
            image[r][c]=color
            fill(r+1,c);fill(r-1,c);fill(r,c+1);fill(r,c-1)
    fill(sr,sc)
    return image
Java
public int[][] floodFill(int[][] img,int sr,int sc,int color){
    int orig=img[sr][sc];
    if(orig==color) return img;
    fill(img,sr,sc,orig,color);
    return img;
}
void fill(int[][] img,int r,int c,int orig,int color){
    if(r<0||r>=img.length||c<0||c>=img[0].length||img[r][c]!=orig) return;
    img[r][c]=color;
    fill(img,r+1,c,orig,color);fill(img,r-1,c,orig,color);
    fill(img,r,c+1,orig,color);fill(img,r,c-1,orig,color);
}

Algorithm Steps

1. Check bounds and color
2. Fill cell
3. Recurse 4 directions
← Previous All Recursion Next →