733. Flood Fill

Problem Description

In this problem, we have a grid that represents an image, where each element in the grid is an integer that symbolizes the pixel value of the image. We're given a starting pixel defined by its row number sr and column number sc, and a new color value color. The task is to perform a "flood fill" on the image beginning from the starting pixel.

A flood fill is akin to pouring paint into a single spot and watching it spread out, coloring all connected areas with the same initial color. The fill spreads only in four directions: up, down, left, and right, from any given pixel. It continues to spread until it encounters a pixel with a different color than the starting pixel's original color.

The objective is to replace the color of the starting pixel and all connected pixels (4-directionally) with the same original color as the starting pixel with the new color. The end result is the image with the modified colors, which we should return.

Intuition

The intuitive approach to solving this problem is to simulate the flooding process using either Depth-First Search (DFS) or Breadth-First Search (BFS). Both are traversal algorithms that can navigate through the grid to find all pixels that are eligible for recoloring.

The intuition behind DFS is to start at the given pixel (sr, sc), change its color to the new color, and then recursively change the color of all adjacent pixels (up, down, left, right) that are the same color as the initial one. This does mean checking whether the new pixel position is within the boundary of the image and whether the pixel color matches the original color of the starting pixel.

For this solution, we'll use DFS:

1. From the starting pixel, update its color to color.
2. Look at adjacent pixels. For each adjacent pixel:
   • If the pixel is within bounds, and
   • If the pixel's color is the same as the starting pixel's original color, and
   • the pixel isn't already the new color (to prevent infinite recursion),
   • then recursively apply the flood fill to that pixel.

The recursive function spreads out from the initial pixel until it has reached all connected pixels with the original color, effectively performing the flood fill and updating the image as required.

Learn more about Depth-First Search and Breadth-First Search patterns.

Solution Approach

The solution employs the Depth-First Search (DFS) algorithm, and the approach can be outlined in the following steps:

1. Initial setup: We define a dfs helper function that will be used to perform the depth-first traversal and paint the image. The image matrix's dimensions are stored in m and n for convenience in bounds checking. The original color (oc) is recorded—it's the color of the starting pixel (at sr, sc).

2. Defining directions: A tuple named dirs is defined, which includes the relative positions that represent the 4-directional moves: up, down, left, and right. The tuple has the pattern (-1, 0, 1, 0, -1) in order to easily loop through pairs of directions for up-down-left-right traversal.

3. Recursion with DFS: The dfs function takes a position (i, j):

   • It checks if the current position is out of bounds or if the pixel's color is not the same as the original color (oc) or is already painted with the new color—this is the base case for the recursion to stop or prevent infinite loops.
   • If the base case does not hold, the current pixel's color is changed to the color.
   • For each 4-directional neighbor (calculated using the dirs tuple), apply DFS recursion by calling dfs on the neighbor's coordinates.

   1def dfs(i, j):
   2    if (
   3        not 0 <= i < m
   4        or not 0 <= j < n
   5        or image[i][j] != oc
   6        or image[i][j] == color
   7    ):
   8        return
   9    image[i][j] = color
   10    for a, b in pairwise(dirs):
   11        dfs(i + a, j + b)

   In the implementation, pairwise(dirs) construct is used (assuming it's similar to Python's pairwise utility to make pairs from the dirs tuple), which should create pairs of directions we want to move in (up, down, left, and right). There is a detail here: most Python environments do not have a built-in function called pairwise. Hence, it's likely meant to be a custom utility defined somewhere else, or an import from some module like itertools. For example, if it was intended as itertools.pairwise(), we would need to import itertools and make sure to handle the last repetitive direction.

4. Initiating the fill: The DFS recursion is initiated by calling dfs(sr, sc).

5. Returning the result: After DFS completes, it returns the image, which by now has been flood-filled using the new color.

The DFS recursion ensures that all connected pixels of the same original color have been recolored, and as the recursion unwinds, the modified image is eventually returned.

Example Walkthrough

Let's consider a small grid as our example image, where we will apply the flood fill algorithm. Suppose the image is a 3x3 grid as follows:

11 1 2
21 1 0
31 0 3

The starting pixel for our flood fill is defined by the row number sr = 1 and column number sc = 1 (using 0-based indexing), and the new color we want to apply is 2.

The pixel at (1, 1) has the color 1. According to the flood fill algorithm, we want to change this color and all connected pixels of the same color to 2.

Step 1: We start from the pixel at (1, 1). Its color is 1, which matches the original color (hence eligible for color change). We change its color to 2.

Our image now looks like this:

11 1 2
21 2 0
31 0 3

Step 2: We perform DFS from our starting pixel. We look at its four neighbors: up (0, 1), down (2, 1), left (1, 0), and right (1, 2).

• Pixel (0, 1) has color 1, so it is eligible. We fill it with color 2.
• Pixel (2, 1) has color 0 and is not eligible since it is not the original color.
• Pixel (1, 0) has color 1, so it is eligible. We fill it with color 2.
• Pixel (1, 2) has color 0 and is not eligible since it is not the original color.

Now our image looks like this:

11 2 2
22 2 0
31 0 3

Step 3: We now apply DFS on the neighbors of these newly colored pixels (0, 1) and (1, 0).

• Checking neighbors of (0, 1): The up and down directions are out of bounds, the left pixel (0, 0) with color 1 gets filled, and the right pixel (0, 2) has color 2.

• Checking neighbors of (1, 0): All sides except the left pixel (1, -1), which is out of bounds, have already been checked or don't have the original color.

Our final image now looks like this:

12 2 2
22 2 0
31 0 3

The image has been successfully filled using the new color 2, starting from the pixel at (1, 1). Pixels connected with the same original color have been recolored, illustrating how the flood fill algorithm works.

Solution Implementation

Time and Space Complexity

The time complexity of the flood fill algorithm is O(M*N), where M is the number of rows and N is the number of columns in the image. This is because in the worst case, the algorithm performs a depth-first search (DFS) on every cell in the grid once when the entire image requires to be filled with the new color.

The space complexity is also O(M*N), primarily due to the recursive stack that could potentially grow to the size of the entire grid in the case of a large connected region with the same color that needs to be filled.

Learn more about how to find time and space complexity quickly using problem constraints.