Flood fill

Easy

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}