Flood Fill

Problem Description

You are given an image represented by an m x n grid of integers image, where image[i][j] represents the pixel value of the image. You are also given three integers sr, sc, and color. Your task is to perform a flood fill on the image starting from the pixel image[sr][sc].

To perform a flood fill:

1. Begin with the starting pixel and change its color to color.
2. Perform the same process for each pixel that is directly adjacent (pixels that share a side with the original pixel, either horizontally or vertically) and shares the same color as the starting pixel.
3. Keep repeating this process by checking neighboring pixels of the updated pixels and modifying their color if it matches the original color of the starting pixel.
4. The process stops when there are no more adjacent pixels of the original color to update.

Return the modified image after performing the flood fill.

Key Insights

• The flood fill operation is similar to a graph traversal problem where each pixel is a node.
• We can use Depth-First Search (DFS) or Breadth-First Search (BFS) to explore all connected pixels of the same color.
• Care must be taken to avoid revisiting pixels to prevent infinite loops.

Space and Time Complexity

Time Complexity: O(m * n) - In the worst case, we may visit every pixel in the grid. Space Complexity: O(m * n) - Space used by the recursive call stack or the queue in BFS.

Solution

To solve the problem, we can implement either a Depth-First Search (DFS) or Breadth-First Search (BFS) approach. Both methods will start from the given pixel (sr, sc) and explore all four possible directions (up, down, left, right).

1. Check if the current pixel is within bounds and matches the original color.
2. Change the color of the current pixel to the new color.
3. Recursively (or iteratively) apply the same process to the adjacent pixels.

Using a visited set or modifying the original image prevents revisiting already colored pixels.

Code Solutions