Flood Fill easy

Problem Statement

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

You are also given three integers sr, sc, and newColor. 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 as the starting pixel), and so on. Replace the color of all these connected pixels with newColor.

Return the modified image after performing the flood fill.

Example 1

Input: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, newColor = 2 Output: [[2,2,2],[2,2,0],[2,0,1]] Explanation: From the center of the image (with position (sr, sc) = (1, 1)), all pixels connected by a path of the same color as the starting pixel are colored with the new color. Note the bottom corner is not colored 2, because it is not 4-directionally connected to the starting pixel.

Example 2

Input: image = [[0,0,0],[0,0,0]], sr = 0, sc = 0, newColor = 2 Output: [[2,2,2],[2,2,2]]

Steps

1. Base Case: If the starting pixel's color is already the newColor, return the image as is. No changes are needed.

2. Recursive Approach (DFS): We use Depth-First Search (DFS) to explore all connected pixels of the same color. The function flood_fill will recursively call itself for adjacent pixels if they share the same color as the starting pixel and haven't been visited yet.

3. Visited Check: Implicitly, we mark pixels as "visited" by changing their color to newColor. This avoids infinite recursion.

4. Boundary Check: Before processing an adjacent pixel, we must check if it is within the bounds of the image.

Explanation

The code uses a recursive Depth-First Search (DFS) approach to traverse the connected component of pixels with the same initial color. The flood_fill_helper function does the recursive work. It checks the bounds, ensures the pixel color matches the original color and then recursively calls itself on the adjacent pixels (up, down, left, right). Each recursive call updates the pixel color to newColor.

Code

def floodFill(image, sr, sc, newColor):
    """
    Performs a flood fill on the given image.

    Args:
        image: A list of lists representing the image.
        sr: The row index of the starting pixel.
        sc: The column index of the starting pixel.
        newColor: The new color to fill with.

    Returns:
        The modified image after the flood fill.
    """
    rows, cols = len(image), len(image[0])
    originalColor = image[sr][sc]

    if originalColor == newColor:
        return image

    def flood_fill_helper(row, col):
        if (row < 0 or row >= rows or
                col < 0 or col >= cols or
                image[row][col] != originalColor):
            return
        image[row][col] = newColor
        flood_fill_helper(row + 1, col)
        flood_fill_helper(row - 1, col)
        flood_fill_helper(row, col + 1)
        flood_fill_helper(row, col - 1)

    flood_fill_helper(sr, sc)
    return image

Complexity

• Time Complexity: O(M * N), where M and N are the dimensions of the image. In the worst case, we visit every pixel.
• Space Complexity: O(M * N) in the worst-case scenario due to the recursive call stack. The space usage can be reduced to O(1) using an iterative approach with a stack or queue instead of recursion.