#733

Easy

auto_awesomeArray plus Depth-First Search

LeetCode Problem Workspace

Flood Fill

Flood Fill is an array and DFS problem where you change connected pixels to a target color efficiently using recursion or BFS.

array depth first search breadth first search matrix

Problem Statement

Given an m x n integer grid representing an image, where image[i][j] is the pixel value, and integers sr, sc, and color, perform a flood fill starting at image[sr][sc]. Change all connected pixels of the same original color to the new color. Connections are only horizontal and vertical.

Return the updated image after performing the flood fill. Ensure you do not change pixels that are not connected to the starting pixel or have a different color.

Examples

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

From the center of the image with position (sr, sc) = (1, 1) (i.e., the red pixel), all pixels connected by a path of the same color as the starting pixel (i.e., the blue pixels) are colored with the new color. Note the bottom corner is not colored 2, because it is not horizontally or vertically connected to the starting pixel.

Example 2

Input: image = [[0,0,0],[0,0,0]], sr = 0, sc = 0, color = 0

Output: [[0,0,0],[0,0,0]]

The starting pixel is already colored with 0, which is the same as the target color. Therefore, no changes are made to the image.

Constraints

m == image.length
n == image[i].length
1 <= m, n <= 50
0 <= image[i][j], color < 216
0 <= sr < m
0 <= sc < n

Solution Approach

Recursive Depth-First Search

Define a recursive DFS function that paints the current pixel if it matches the original color, then calls itself on all four neighbors. Terminate recursion when out of bounds or color differs.

Iterative Breadth-First Search

Use a queue to track pixels to visit. Pop a pixel, paint it, then enqueue valid neighbors with the same original color. This avoids stack overflow on large grids.

Boundary and Revisit Handling

Always check that indices are within the grid and that the pixel has the original color before painting. Optionally, mark visited pixels to prevent redundant operations.

Complexity Analysis

Metric	Value
Time	O(N)
Space	O(N)

Time complexity is O(N) where N is total pixels, as each pixel is visited once. Space complexity is O(N) in worst case due to recursion stack or queue storage.

What Interviewers Usually Probe

Checks if you recognize that a recursive DFS naturally models connected components in a grid.
Looks for handling of edge conditions like starting pixel already having target color.
Wants to see whether BFS alternative is considered for avoiding deep recursion stack.

Common Pitfalls or Variants

Common pitfalls

Modifying pixels before checking color can paint unintended areas.
Failing to handle the starting pixel being the same as the target color can cause infinite recursion.
Ignoring boundary conditions leads to index errors.

Follow-up variants

Use DFS with diagonal connections to extend flood fill to 8-direction connectivity.
Perform flood fill on a 3D matrix for volumetric image processing.
Implement color replacement with constraints, such as only changing pixels within a certain distance.

FAQ

What is the main pattern used in the Flood Fill problem?

The primary pattern is Array plus Depth-First Search, as you explore all connected pixels recursively or iteratively.

Can I use BFS instead of DFS for Flood Fill?

Yes, BFS is valid and often used to avoid stack overflow in large grids while achieving the same result.

What should I do if the starting pixel already has the target color?

Skip any operation and return the image immediately to prevent unnecessary recursion or queue processing.

Does Flood Fill consider diagonal connections?

By default, only horizontal and vertical connections are considered; diagonals are a variant extension.

What is the time and space complexity of Flood Fill?

Time complexity is O(N) where N is the number of pixels, and space complexity is O(N) due to recursion stack or queue.

terminal

Solution

Solution 1: DFS

We denote the initial pixel's color as $\textit{oc}$. If $\textit{oc}$ is not equal to the target color $\textit{color}$, we start a depth-first search from $(\textit{sr}, \textit{sc})$ to change the color of all eligible pixels to the target color.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def floodFill(
        self, image: List[List[int]], sr: int, sc: int, color: int
    ) -> List[List[int]]:
        def dfs(i: int, j: int):
            image[i][j] = color
            for a, b in pairwise(dirs):
                x, y = i + a, j + b
                if 0 <= x < len(image) and 0 <= y < len(image[0]) and image[x][y] == oc:
                    dfs(x, y)

        oc = image[sr][sc]
        if oc != color:
            dirs = (-1, 0, 1, 0, -1)
            dfs(sr, sc)
        return image

Solution 2: BFS

We first check if the initial pixel's color is equal to the target color. If it is, we return the original image directly. Otherwise, we can use the breadth-first search method, starting from $(\textit{sr}, \textit{sc})$, to change the color of all eligible pixels to the target color.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def floodFill(
        self, image: List[List[int]], sr: int, sc: int, color: int
    ) -> List[List[int]]:
        def dfs(i: int, j: int):
            image[i][j] = color
            for a, b in pairwise(dirs):
                x, y = i + a, j + b
                if 0 <= x < len(image) and 0 <= y < len(image[0]) and image[x][y] == oc:
                    dfs(x, y)

        oc = image[sr][sc]
        if oc != color:
            dirs = (-1, 0, 1, 0, -1)
            dfs(sr, sc)
        return image

Continue Practicing

#749 contain virus #695 max area of island #778 swim in rising water