Flood Fill

The problem description can be found in LeetCode.

Approach

Sometimes Graph problems are hidden by other representations. In fact, the input matrix we can find in the first example can be thought as a Graph.

In this case, we don't need to derive any Adjacency List. In fact, we can directly calculate the neighbors by getting the values directly connected at the top, bottom, left and right.

Once we get the neighbors, we could add them to a Stack and process them later if their color matches the one at [sr][sc].

Solution

from typing import List


class Solution:
    def floodFill(
        self, image: List[List[int]], sr: int, sc: int, color: int
    ) -> List[List[int]]:
        old_color = image[sr][sc]
        if old_color == color:
            return image

        rows, cols = len(image), len(image[0])
        stack = [(sr, sc)]
        deltas = [
            (-1, 0),  # up
            (+1, 0),  # down
            (0, -1),  # left
            (0, +1),  # right
        ]
        while stack:
            row, col = stack.pop()
            image[row][col] = color

            for d_row, d_col in deltas:
                new_row = row + d_row
                new_col = col + d_col

                if (
                    0 <= new_row < rows
                    and 0 <= new_col < cols
                    and image[new_row][new_col] == old_color
                ):
                    stack.append((new_row, new_col))

        return image

Complexity

• Time: $O(mn)$
• Space: $O(mn)$

Where $m$ and $n$ are the number of rows and columns of the input image, respectively.