Flood Fill

GraphsDFS

20 min

Problem Statement

An image is represented by an m x n integer grid image where image[i][j] represents the pixel value of the image.

You are also given three integers sr, sc, and color. You should perform a flood fill on the image starting from the pixel image[sr][sc].

To perform a flood fill, consider the starting pixel, plus any pixels connected 4-directionally to the starting pixel of the same color as the starting pixel, plus any pixels connected 4-directionally to those pixels (also with the same color), and so on. Replace the color of all of the aforementioned pixels with color.

Example

Example 1:

sr = 1, sc = 1, color = 2

Output:

Solution

This problem is another classic graph traversal, very similar to "Number of Islands". We can treat the grid of pixels as a graph where each pixel is a node. We need to find all pixels connected to the starting pixel `(sr, sc)` that have the same original color.

A Depth-First Search (DFS) is a natural fit here. We start at the given pixel, change its color, and then recursively call our DFS function on all its 4-directional neighbors that have the same original color.

Algorithm Steps (DFS)

Store the `originalColor` of the starting pixel `image[sr][sc]`.
If `originalColor` is already the new `color`, no changes are needed, so return the image.
Create a recursive DFS helper function that takes the current pixel's row and column.
In the DFS function, check for boundary conditions (out of bounds) or if the current pixel's color is not the `originalColor`. If so, return.
Change the current pixel's color to the new `color`.
Recursively call the DFS function for all 4 adjacent neighbors.
Initiate the process by calling the DFS function on the starting pixel `(sr, sc)`.

Flood Fill Visualization

Progress1 / 1

Ready to start.

Flood Fill (DFS)


class Solution:
    def floodFill(self, image: list[list[int]], sr: int, sc: int, color: int) -> list[list[int]]:
        original_color = image[sr][sc]
        if original_color == color:
            return image
        
        rows, cols = len(image), len(image[0])
        
        def dfs(r, c):
            if (r < 0 or c < 0 or
                r >= rows or c >= cols or
                image[r][c] != original_color):
                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