Lesson

13.13Flood Fill

Problem Statement

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:

Begin with the starting pixel and change its color to color.
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.
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.
Stop when there are no more adjacent pixels of the original color to update.

Return the modified image after performing the flood fill.

Note:

In a path, no cell can be visited more than one time.
If the source cell is 0, the rat cannot move to any other cell.
In case of no path, return an empty list.

Example Inputs

Example 1:

Example 2:

Example 3:

Problem Solution

Approach

To perform a flood fill on the image, we can use a Depth-First Search (DFS) approach. The idea is to start from the given starting cell (sr, sc) and recursively explore all adjacent cells that have the same color as the starting cell. During the traversal, we change the color of each visited cell to the target color. To avoid revisiting the same cell, we mark cells as visited by altering their color during the traversal.

Steps

Initial Check:
- If the color of the starting cell image[sr][sc] is already equal to the target color, there's nothing to change. Return the original image.
Define Directions:
- Define the four possible directions the rat can move: Up ('U'), Down ('D'), Left ('L'), and Right ('R').
Recursive DFS Function (dfs):
- Parameters:
  - i: Current row index.
  - j: Current column index.
  - originalColor: The original color of the starting cell.
  - color: The new color to apply.
  - image: The grid representing the image.
- Base Cases:
  - If (i, j) is out of bounds, return.
  - If the current cell image[i][j] is not equal to originalColor, return.
  - If the current cell is already the target color, return to prevent infinite recursion.
- Action:
  - Change the color of the current cell to the target color.
- Recursive Calls:
  - Recursively call dfs for all four adjacent cells (Up, Down, Left, Right).
- Backtracking:
  - No explicit backtracking is needed since we are changing the color in place. Once the recursion returns, other paths will handle their own color changes.
Initiate DFS:
- Call the dfs function starting from the cell (sr, sc).
Return the Result:
- After the DFS traversal, return the modified image.

Time & Space Complexity

Time Complexity: O(m * n)
- In the worst case, where all cells are connected and have the same color as the starting cell, we visit each cell once.
Space Complexity: O(m * n)
- The recursion stack can go as deep as the number of cells in the image in the worst case.

Code Snippet

Dry Run

Let's perform a dry run with the following input:

Goal: Perform a flood fill starting from (0, 0) and change connected cells with the same color to 2.

Steps:

Initial Check:
- originalColor = image[0][0] = 1
- Since originalColor (1) !== color (2), proceed.
Start DFS from (0, 0)
- Change image[0][0] to 2.
- Current Image:

Explore Up: (0-1, 0) = (-1, 0) → Out of bounds. Return.
Explore Down: (0+1, 0) = (1, 0)
- image[1][0] = 1 → Same as originalColor.
- Change image[1][0] to 2.
- Current Image:

 - **Explore Up:** `(1-1, 0) = (0, 0)`
   - `image[0][0] = 2` → Not equal to `originalColor (1)`. Return.
 - **Explore Down:** `(1+1, 0) = (2, 0)`
   - `image[2][0] = 1` → Same as `originalColor`.
   - Change `image[2][0]` to `2`.
   - Current Image:

   - **Explore Up:** `(2-1, 0) = (1, 0)`
     - `image[1][0] = 2` → Not equal to `originalColor (1)`. Return.
   - **Explore Down:** `(2+1, 0) = (3, 0)`
     - `image[3][0] = 0` → Blocked. Return.
   - **Explore Left:** `(2, 0-1) = (2, -1)` → Out of bounds. Return.
   - **Explore Right:** `(2, 0+1) = (2, 1)`
     - `image[2][1] = 1` → Same as `originalColor`.
     - Change `image[2][1]` to `2`.
     - Current Image:

     - **Explore Up:** `(2-1, 1) = (1, 1)`
       - `image[1][1] = 1` → Same as `originalColor`.
       - Change `image[1][1]` to `2`.
       - Current Image:

       - **Explore Up:** `(1-1, 1) = (0, 1)`
         - `image[0][1] = 0` → Blocked. Return.
       - **Explore Down:** `(1+1, 1) = (2, 1)`
         - `image[2][1] = 2` → Not equal to `originalColor (1)`. Return.
       - **Explore Left:** `(1, 1-1) = (1, 0)`
         - `image[1][0] = 2` → Not equal to `originalColor (1)`. Return.
       - **Explore Right:** `(1, 1+1) = (1, 2)`
         - `image[1][2] = 0` → Blocked. Return.

       - **Backtrack:** Restore `image[1][1]` to `1`.
       - Current Image:

     - **Explore Down:** `(2+1, 1) = (3, 1)`
       - `image[3][1] = 1` → Same as `originalColor`.
       - Change `image[3][1]` to `2`.
       - Current Image:

       - **Explore Up:** `(3-1, 1) = (2, 1)`
         - `image[2][1] = 2` → Not equal to `originalColor (1)`. Return.
       - **Explore Down:** `(3+1, 1) = (4, 1)` → Out of bounds. Return.
       - **Explore Left:** `(3, 1-1) = (3, 0)`
         - `image[3][0] = 0` → Blocked. Return.
       - **Explore Right:** `(3, 1+1) = (3, 2)`
         - `image[3][2] = 1` → Same as `originalColor`.
         - Change `image[3][2]` to `2`.
         - Current Image:

         - **Explore Up:** `(3-1, 2) = (2, 2)`
           - `image[2][2] = 0` → Blocked. Return.
         - **Explore Down:** `(3+1, 2) = (4, 2)` → Out of bounds. Return.
         - **Explore Left:** `(3, 2-1) = (3, 1)`
           - `image[3][1] = 2` → Not equal to `originalColor (1)`. Return.
         - **Explore Right:** `(3, 2+1) = (3, 3)`
           - `image[3][3] = 1` → Same as `originalColor`.
           - Change `image[3][3]` to `2`.
           - Current Image:

           - **Explore Up:** `(3-1, 3) = (2, 3)`
             - `image[2][3] = 0` → Blocked. Return.
           - **Explore Down:** `(3+1, 3) = (4, 3)` → Out of bounds. Return.
           - **Explore Left:** `(3, 3-1) = (3, 2)`
             - `image[3][2] = 2` → Not equal to `originalColor (1)`. Return.
           - **Explore Right:** `(3, 3+1) = (3, 4)` → Out of bounds. Return.

           - **Backtrack:** Restore `image[3][3]` to `1`.
           - Current Image:

         - **Backtrack:** Restore `image[3][2]` to `1`.
         - Current Image:

       - **Backtrack:** Restore `image[3][1]` to `1`.
       - Current Image:

     - **Explore Left:** `(2, 1-1) = (2, 0)`
       - `image[2][0] = 2` → Not equal to `originalColor (1)`. Return.
     - **Explore Right:** `(2, 1+1) = (2, 2)`
       - `image[2][2] = 0` → Blocked. Return.

     - **Backtrack:** Restore `image[2][1]` to `1`.
     - Current Image:

   - **Backtrack:** Restore `image[2][1]` and `image[2][0]`.
   - Current Image:

 - **Explore Left:** `(1, 0-1) = (1, -1)` → Out of bounds. Return.
 - **Explore Right:** `(1, 0+1) = (1, 1)`
   - `image[1][1] = 1` → Same as `originalColor`.
   - Change `image[1][1]` to `2`.
   - Current Image:

   - **Explore Up:** `(1-1, 1) = (0, 1)`
     - `image[0][1] = 0` → Blocked. Return.
   - **Explore Down:** `(1+1, 1) = (2, 1)`
     - `image[2][1] = 1` → Same as `originalColor`.
     - Change `image[2][1]` to `2`.
     - Current Image:

     - **Explore Up:** `(2-1, 1) = (1, 1)`
       - `image[1][1] = 2` → Not equal to `originalColor (1)`. Return.
     - **Explore Down:** `(2+1, 1) = (3, 1)`
       - `image[3][1] = 1` → Same as `originalColor`.
       - Change `image[3][1]` to `2`.
       - Current Image:

       - **Explore Up:** `(3-1, 1) = (2, 1)`
         - `image[2][1] = 2` → Not equal to `originalColor (1)`. Return.
       - **Explore Down:** `(3+1, 1) = (4, 1)` → Out of bounds. Return.
       - **Explore Left:** `(3, 1-1) = (3, 0)`
         - `image[3][0] = 0` → Blocked. Return.
       - **Explore Right:** `(3, 1+1) = (3, 2)`
         - `image[3][2] = 1` → Same as `originalColor`.
         - Change `image[3][2]` to `2`.
         - Current Image:

         - **Explore Up:** `(3-1, 2) = (2, 2)`
           - `image[2][2] = 0` → Blocked. Return.
         - **Explore Down:** `(3+1, 2) = (4, 2)` → Out of bounds. Return.
         - **Explore Left:** `(3, 2-1) = (3, 1)`
           - `image[3][1] = 2` → Not equal to `originalColor (1)`. Return.
         - **Explore Right:** `(3, 2+1) = (3, 3)`
           - `image[3][3] = 1` → Same as `originalColor`.
           - Change `image[3][3]` to `2`.
           - Current Image:

           - **Explore Up:** `(3-1, 3) = (2, 3)`
             - `image[2][3] = 0` → Blocked. Return.
           - **Explore Down:** `(3+1, 3) = (4, 3)` → Out of bounds. Return.
           - **Explore Left:** `(3, 3-1) = (3, 2)`
             - `image[3][2] = 2` → Not equal to `originalColor (1)`. Return.
           - **Explore Right:** `(3, 3+1) = (3, 4)` → Out of bounds. Return.

           - **Backtrack:** Restore `image[3][3]` to `1`.
           - Current Image:

         - **Backtrack:** Restore `image[3][2]` to `1`.
         - Current Image:

       - **Backtrack:** Restore `image[3][1]` to `1`.
       - Current Image:

     - **Explore Left:** `(2, 1-1) = (2, 0)`
       - `image[2][0] = 2` → Not equal to `originalColor (1)`. Return.
     - **Explore Right:** `(2, 1+1) = (2, 2)`
       - `image[2][2] = 0` → Blocked. Return.

     - **Backtrack:** Restore `image[2][1]` to `1`.
     - Current Image:

   - **Backtrack:** Restore `image[1][1]` to `1`.
   - Current Image:

 - **Explore Right:** `(1, 1+1) = (1, 2)`
   - `image[1][2] = 0` → Blocked. Return.

 - **Backtrack:** Restore `image[1][0]` to `1`.
 - Current Image:

Continue Iterating Through the Grid:
- Starting from other cells with 1 will either lead to blocked paths or paths with lower total gold.
Final Result:
- image after flood fill:

  - The maximum gold collected is `24`.

Complexity Analysis

Time Complexity: O(m * n)
- In the worst case, where all cells are connected and have the same color as the starting cell, we visit each cell once.
Space Complexity: O(m * n)
- The recursion stack can go as deep as the number of cells in the image in the worst case.

Optimizations:

Early Termination:
- If the original color is the same as the target color, we immediately return the image without performing any operations, saving unnecessary computations.
In-Place Modification:
- By modifying the image in place, we avoid using additional space for tracking visited cells.

Conclusion

The Flood Fill problem is a classic example of using Depth-First Search (DFS) to explore and modify connected components within a grid. By systematically traversing the grid from a starting point and updating the color of each reachable cell, we can efficiently perform the flood fill operation.

Understanding this approach not only helps in solving similar grid-based traversal and modification problems but also reinforces fundamental concepts in recursion, DFS, and in-place algorithm optimization. Implementing the solution in a functional style without using classes makes the code more concise and easier to understand, especially for those new to programming. By carefully managing the traversal state and ensuring boundary and color checks, complex flood fill operations become manageable and executable with clarity and confidence.

Previous Next