Flood fill
Problem
Given an image grid, a start pixel (sr, sc) and a new colour, recolour the start pixel and every pixel connected to it (up, down, left or right) that has the same original colour. Return the image.
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]]
Also asked as: flood fill algo
Test cases
Case 1
Input: [[1,1,1],[1,1,0],[1,0,1]], 1, 1, 2 Expected: [[2,2,2],[2,2,0],[2,0,1]]
Case 2
Input: [[0,0,0],[0,0,0]], 0, 0, 0 Expected: [[0,0,0],[0,0,0]]
Case 3
Input: [[1]], 0, 0, 5 Expected: [[5]]
View solutionHide solution1 approach
1. DFS/BFS from the start pixel
Time O(R·C)Space O(R·C)
Recolour the start pixel and recurse into 4-connected neighbours that still have the original colour.
function floodFill(image, sr, sc, newColor) { const old = image[sr][sc]; if (old === newColor) return image; const fill = (r, c) => { if (r < 0 || c < 0 || r >= image.length || c >= image[0].length || image[r][c] !== old) return; image[r][c] = newColor; fill(r + 1, c); fill(r - 1, c); fill(r, c + 1); fill(r, c - 1); }; fill(sr, sc); return image;}