Flood Fill - BFS

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.

Example 1:

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]]
Explanation: From the center of the image with position (sr, sc) = (1, 1) (i.e., the red pixel), all pixels connected by a path of the same color as the starting pixel (i.e., the blue pixels) 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, color = 0
Output: [[0,0,0],[0,0,0]]
Explanation: The starting pixel is already colored 0, so no changes are made to the image.

---

1) Explain the problem

The problem is to implement the flood fill algorithm. Given an image represented by a 2D grid of pixel values, and starting from a specific pixel (sr, sc), you need to change the color of that pixel and all connected pixels (up, down, left, right) with the same original color to a new given color.

2) Short easy to remember solution/approach

• If the starting pixel already has the new color, return the image as is.

• Use Depth-First Search (DFS) to explore and change the color of the starting pixel and all 4-directionally connected pixels with the same original color.

3) Solution in JavaScript with code commenting

function floodFill(image, sr, sc, newColor) {
    const originalColor = image[sr][sc];
    if (originalColor === newColor) return image;

    const fill = (r, c) => {
        // If the pixel is out of bounds or not the original color, return
        if (r < 0 || r >= image.length || c < 0 || c >= image[0].length || image[r][c] !== originalColor) {
            return;
        }

        // Change the color of the pixel
        image[r][c] = newColor;

        // Recursively fill the surrounding pixels
        fill(r + 1, c);
        fill(r - 1, c);
        fill(r, c + 1);
        fill(r, c - 1);
    };

    // Start the flood fill from the initial pixel
    fill(sr, sc);

    return image;
}

4) Explanation of the solution in an easy-to-understand way with a real-life example

Imagine you have a coloring book page with a large white area (a region) that you want to color blue. You start from a specific white spot, and you want to ensure that the entire connected white area is turned blue. You go to that spot, start coloring it blue, and then move to its neighboring white spots, continuing the process until the entire connected white area is blue. This is similar to how the flood fill algorithm works.

5) Code explanation in pointers

• Initialize: Store the original color of the starting pixel.

• Base Case: If the starting pixel already has the new color, return the image as it is.

• Recursive Function (fill):

  • Boundary Check: Ensure the pixel is within bounds and matches the original color.

  • Color Change: Change the pixel's color to the new color.

  • Recursion: Recursively call the function for the four neighboring pixels (up, down, left, right).

• Start Flood Fill: Begin the flood fill process from the starting pixel (sr, sc).

6) Complexities

• Time Complexity: O(m * n) where m is the number of rows and n is the number of columns in the image. In the worst case, every pixel may be visited once.

• Space Complexity: O(m * n) for the call stack in the worst case due to recursion.

---