LeetCode 733: Flood Fill in Python — DFS Solution

LeetCode 733, Flood Fill, asks you to recolor the connected component containing a starting pixel. The graph is implicit: each image cell is a node, and its up, down, left, and right neighbors are edges.

Python depth-first search solution

from typing import List

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

        def visit(row: int, col: int) -> None:
            if (row < 0 or row == len(image) or col < 0 or
                    col == len(image[0]) or image[row][col] != original):
                return
            image[row][col] = color
            visit(row + 1, col)
            visit(row - 1, col)
            visit(row, col + 1)
            visit(row, col - 1)

        visit(sr, sc)
        return image

Why the early return matters

Recoloring a cell is also the visited marker. If original == color, that marker never changes and recursion would repeatedly revisit the same cells. Return before traversing in that case.

Complexity and alternatives

Each cell is visited at most once, so time is O(rows × columns). Recursive DFS can use the same amount of call-stack space in the worst case. For a large image, use an explicit stack or collections.deque for iterative DFS/BFS to avoid Python’s recursion limit.

Tests that catch mistakes

• A one-cell image.
• A start pixel already holding the requested color.
• A component touching all four borders.
• Different-colored cells that block diagonal travel; diagonals are not connected in this problem.

Problem reference: LeetCode 733: Flood Fill.