Flood Fill

Clarify the problem:

• The problem requires implementing a flood fill algorithm to fill a given area with a new color.
• We are given an image represented as a 2D array of integers, each representing a color.
• We need to replace the color of a given starting pixel and all its adjacent pixels of the same color with a new color.
• The flood fill should propagate through the image, filling all connected pixels of the same color.
• The starting pixel's color and the new color are provided as input.

Analyze the problem:

• Input: A 2D array representing an image, the starting pixel coordinates, the starting color, and the new color.
• Output: The modified image with the filled area.
• Constraints:
  • The image is represented as a rectangular 2D array.
  • The dimensions of the image can be up to 50x50.
  • The starting pixel coordinates are within the image boundaries.
  • The starting color and the new color are integers.

Design an algorithm:

• We can solve this problem using a recursive approach.
• The algorithm can be implemented as a recursive function called floodFill.
• In the floodFill function, we will check if the current pixel matches the starting color.
• If it does, we will change its color to the new color and recursively call the floodFill function on its neighboring pixels.
• We need to handle the boundaries of the image properly to avoid going out of bounds.
• To prevent revisiting the same pixel multiple times, we can use a visited array to track the visited pixels.

Explain your approach:

• We will implement a function called floodFill that takes the image, starting pixel coordinates, starting color, and new color as input.
• The function will check if the current pixel matches the starting color.
• If it does, we will change its color to the new color and recursively call the floodFill function on its neighboring pixels.
• We will handle the boundaries of the image by checking if the current pixel coordinates are within the image boundaries.
• To avoid revisiting the same pixel, we will use a visited array to track the visited pixels.

Write clean and readable code:

python

def floodFill(image, sr, sc, newColor):
    startColor = image[sr][sc]
    visited = [[False for _ in range(len(image[0]))] for _ in range(len(image))]

    def dfs(row, col):
        if (
            row < 0
            or row >= len(image)
            or col < 0
            or col >= len(image[0])
            or image[row][col] != startColor
            or visited[row][col]
        ):
            return

        visited[row][col] = True
        image[row][col] = newColor

        dfs(row - 1, col)  # Up
        dfs(row + 1, col)  # Down
        dfs(row, col - 1)  # Left
        dfs(row, col + 1)  # Right

    dfs(sr, sc)
    return image

Test your code:

• To test the code, we can create a sample image and call the floodFill function with different starting pixels and colors.
• Test case 1:

python

image = [[0, 0, 0], [0, 1, 1]]
sr = 1
sc = 1
newColor = 2
print(floodFill(image, sr, sc, newColor))
# Output: [[0, 0, 0], [0, 2, 2]]

Optimize if necessary:

• The provided implementation follows a straightforward and optimal approach for the flood fill algorithm.
• The time complexity of the algorithm is O(N), where N is the number of pixels in the image.
• This is because we visit each pixel once and perform a constant amount of work at each pixel.

Handle error cases:

• The code assumes that the input image is not empty and that the starting pixel coordinates are valid.
• If the image is empty or the starting pixel coordinates are out of bounds, the code will not work correctly.
• We can handle these error cases by adding appropriate checks at the beginning of the floodFill function to return the image unchanged or raise an error.

Discuss complexity analysis:

• Time complexity: The algorithm has a time complexity of O(N), where N is the number of pixels in the image. We visit each pixel once and perform a constant amount of work at each pixel.
• Space complexity: The space complexity is O(N), where N is the number of pixels in the image. We use the visited array to track the visited pixels, which requires O(N) space. Additionally, the recursion stack has a maximum depth of N in the worst case, which also contributes to the space complexity.