Flood Fill

01 · Question

An image is represented by an m x n integer grid image where image[i][j] represents the pixel value. Perform a flood fill starting from (sr, sc), replacing the starting pixel's color and all connected pixels of the same color with color.

Example:

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

02 · Solution

Reference solution

1def floodFill(image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
2    rows, cols = len(image), len(image[0])
3    start = image[sr][sc]
4    if start == color:
5        return image
6    
7    def dfs(r: int, c: int) -> None:
8        if r < 0 or r >= rows or c < 0 or c >= cols:
9            return
10        if image[r][c] != start:
11            return
12        image[r][c] = color
13        dfs(r + 1, c)
14        dfs(r - 1, c)
15        dfs(r, c + 1)
16        dfs(r, c - 1)
17    
18    dfs(sr, sc)
19    return image

Number of Islands

Rotting Oranges