Flood Fill

Given an image (2D int array), starting pixel (sr,sc), and new color, perform flood fill (like paint bucket tool). All connected pixels with the same starting color get the new color.

Example 1

Input: 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]]

Solution Approach

DFS/BFS from (sr,sc). If the color is already new color, return. Otherwise, recursively fill same-colored neighbors.

If image[sr][sc]==color, return (already filled).
BFS from (sr,sc): change color, add 4-directional neighbors with original color.

Java

import java.util.*;

class Solution {
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        int orig = image[sr][sc];
        if (orig == color) return image;
        int m=image.length, n=image[0].length;
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{sr,sc}); image[sr][sc]=color;
        int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
        while (!q.isEmpty()) {
            int[] cur=q.poll();
            for (int[] d:dirs) {
                int r=cur[0]+d[0],c=cur[1]+d[1];
                if (r>=0&&r<m&&c>=0&&c<n&&image[r][c]==orig) { image[r][c]=color; q.offer(new int[]{r,c}); }
            }
        }
        return image;
    }
}

Time Complexity: O(M*N)
Space Complexity: O(M*N)