LeetCode 733: Flood Fill

Problem Restatement

We are given an image represented as a 2D grid of integers.

Each integer is a pixel color.

We are also given:

sr
sc
color

sr and sc describe the starting pixel:

image[sr][sc]

We need to perform a flood fill from that starting pixel.

Flood fill changes the starting pixel and every pixel connected to it with the same original color.

Connection is only 4-directional:

up
down
left
right

Diagonal pixels are not connected.

At the end, return the modified image. The official statement defines the image as a 2D integer array and asks us to recolor the starting pixel plus all 4-directionally connected pixels with the same original color.

Input and Output

Example function shape:

def floodFill(image: list[list[int]], sr: int, sc: int, color: int) -> list[list[int]]:
    ...

Examples

Example 1

image = [
    [1, 1, 1],
    [1, 1, 0],
    [1, 0, 1],
]
sr = 1
sc = 1
color = 2

The starting pixel is:

image[1][1] == 1

So the original color is 1.

We recolor all 1 pixels connected to (1, 1) through up, down, left, or right moves.

The result is:

[
    [2, 2, 2],
    [2, 2, 0],
    [2, 0, 1],
]

The bottom-right 1 stays unchanged because it is diagonal from a filled region and cannot be reached through 4-directional moves.

Example 2

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

The original color is already 0.

The new color is also 0.

The image does not need to change:

[
    [0, 0, 0],
    [0, 0, 0],
]

This case matters because without an early return, DFS may keep revisiting pixels forever.

First Thought: Traverse the Connected Region

This is a grid connectivity problem.

Each pixel is like a node in a graph.

There is an edge between two pixels if they are adjacent up, down, left, or right.

We need to visit the connected component that starts at (sr, sc) and contains only pixels with the same original color.

Depth-first search is a natural fit.

Key Insight

Save the original color first:

original = image[sr][sc]

Then DFS should only enter a cell if:

1. The row is inside the grid.
2. The column is inside the grid.
3. The cell still has the original color.

When a valid cell is found, recolor it immediately.

That recoloring also marks the cell as visited.

So we do not need a separate visited set, as long as original != color.

Algorithm

1. Store the original color at the starting pixel.
2. If the original color equals the new color, return image.
3. Define a DFS function dfs(r, c).
4. In dfs, stop if (r, c) is out of bounds.
5. Stop if image[r][c] != original.
6. Otherwise, set image[r][c] = color.
7. Recursively visit the four neighbors.
8. Return the modified image.

Correctness

The DFS starts at the given pixel (sr, sc). Since this pixel has the original color, it is part of the region that must be recolored.

Whenever DFS visits a pixel, it first checks that the pixel lies inside the image and has the original color. Therefore, DFS never recolors a pixel outside the image, and it never recolors a pixel with a different color.

After a pixel is recolored, DFS recursively explores its four neighbors. Therefore, any pixel reachable from the start through a path of 4-directionally adjacent original-color pixels will eventually be visited and recolored.

Pixels outside this connected component cannot be reached by such a path, so DFS never recolors them.

Thus the algorithm recolors exactly the required connected component and returns the correct image.

Complexity

Let m be the number of rows and n be the number of columns.

The image is modified in place.

Implementation

class Solution:
    def floodFill(
        self,
        image: list[list[int]],
        sr: int,
        sc: int,
        color: int,
    ) -> list[list[int]]:
        rows = len(image)
        cols = len(image[0])
        original = image[sr][sc]

        if original == color:
            return image

        def dfs(r: int, c: int) -> None:
            if r < 0 or r >= rows:
                return

            if c < 0 or c >= cols:
                return

            if image[r][c] != original:
                return

            image[r][c] = color

            dfs(r + 1, c)
            dfs(r - 1, c)
            dfs(r, c + 1)
            dfs(r, c - 1)

        dfs(sr, sc)

        return image

Code Explanation

We first read the grid size:

rows = len(image)
cols = len(image[0])

Then we save the starting color:

original = image[sr][sc]

This is the only color that may be replaced.

If the new color is the same as the original color, there is no work to do:

if original == color:
    return image

This also prevents repeated recursion over already unchanged cells.

The DFS rejects invalid positions:

if r < 0 or r >= rows:
    return

if c < 0 or c >= cols:
    return

It also rejects cells that are not part of the original-color component:

if image[r][c] != original:
    return

When a cell is valid, we recolor it:

image[r][c] = color

Then we visit the four adjacent cells:

dfs(r + 1, c)
dfs(r - 1, c)
dfs(r, c + 1)
dfs(r, c - 1)

Testing

def run_tests():
    s = Solution()

    image = [
        [1, 1, 1],
        [1, 1, 0],
        [1, 0, 1],
    ]

    assert s.floodFill(image, 1, 1, 2) == [
        [2, 2, 2],
        [2, 2, 0],
        [2, 0, 1],
    ]

    image = [
        [0, 0, 0],
        [0, 0, 0],
    ]

    assert s.floodFill(image, 0, 0, 0) == [
        [0, 0, 0],
        [0, 0, 0],
    ]

    image = [[1]]
    assert s.floodFill(image, 0, 0, 2) == [[2]]

    image = [
        [1, 0, 1],
        [0, 1, 0],
        [1, 0, 1],
    ]

    assert s.floodFill(image, 1, 1, 2) == [
        [1, 0, 1],
        [0, 2, 0],
        [1, 0, 1],
    ]

    print("all tests passed")

run_tests()