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.

Return the modified image after performing the flood fill.

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

Python Solution

DFS: Recursive

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

        ROWS, COLS = len(image), len(image[0])
        s_color = image[sr][sc]
        n_color = color

        # Return the original image if the start color == new color
        if s_color == n_color:
            return image
        
        def dfs(image, ro, co, s_color, n_color):
            # Paint the cell if it is the start color
            if image[ro][co] == s_color:
                image[ro][co] = n_color

                # Move up, right, down, left
                for dr, dc in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
                    r = ro + dr
                    c = co + dc
                    # If the move is valid and the cell is the start color
                    if 0 <= r < ROWS and 0 <= c < COLS and image[r][c] == s_color:
                        dfs(image, r, c, s_color, n_color)
        
        dfs(image, sr, sc, s_color, n_color)

        return image

Due to the recursive limits in Python, the iterative approach is superior.

DFS: Iterative

from collections import deque
class Solution:
    def floodFill(self, 
            image: List[List[int]], 
            sr: int, 
            sc: int, 
            color: int) -> List[List[int]]:

        ROWS, COLS = len(image), len(image[0])
        s_color = image[sr][sc]
        n_color = color

        # Return the original image if start color == new color
        if s_color == n_color:
            return image

        # Add the start coordinates to the stack
        stack = deque([(sr, sc)])

        while stack:
            ro, co = stack.pop()
            # If cell is the start color, paint it the new color
            if image[ro][co] == s_color:
                image[ro][co] = n_color

                # Traverse up, right, down, and left
                # (Note: We add the direcitons to the stack 
                #        in the reverse order)
                for dr, dc in [(0, -1), (1, 0),  (0, 1), (-1, 0)]:
                    r = ro + dr
                    c = co + dc
                    # If move is valid and the next cell is the start color
                    if 0 <= r < ROWS and 0 <= c < COLS and image[r][c] == s_color:
                        stack.append((r, c))

        return image