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.
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]]
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.
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)