Flood Fill

Identifying Problem Isomorphism

“Flood Fill” is isomorphic to “Island Perimeter”.

In “Flood Fill”, you’re given a 2D grid with integers denoting different colors. Given a position and a new color, you have to replace the color of the position and all of its adjacent cells (that share the same initial color) with the new color. The exploration can be done using depth-first search (DFS) or breadth-first search (BFS).

In “Island Perimeter”, you’re given a 2D grid filled with 0’s (water) and 1’s (land), where 1’s form a connected island (not necessarily rectangular). You have to find the perimeter of this island. This problem can also be solved by scanning the entire grid and for each land cell, looking at its four neighbors to calculate the perimeter.

The reason is that both problems involve the exploration of a grid to find connected cells with the same property (color in “Flood Fill” and land in “Island Perimeter”). Both use similar strategies to traverse the grid. The mapping is an approximate one, as the goal of exploration and the properties of the cells being explored differ.

This problem is a DFS problem where we want to explore all the connected nodes (pixels) having the same color and change their color to the new color. In each recursive call, we first check if the current pixel has the same color as the original pixel (start pixel) and is within the image boundaries. If it is, we then change the color of the current pixel to the new color and make recursive calls to the neighboring pixels (up, down, left, and right).

Iterative solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution:

    def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
        """Performs a flood fill on the image starting from the pixel image[sr][sc].

        Args:
            image: The image to be flood filled.
            sr: The row index of the starting pixel.
            sc: The column index of the starting pixel.
            color: The new color for the flood fill.

        Returns:
            The modified image after performing the flood fill.
        """

        old_color = image[sr][sc]
        if old_color == color:
            return image

        queue = [(sr, sc)]
        while queue:
            r, c = queue.pop(0)
            image[r][c] = color
            for nr, nc in [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]:
                if 0 <= nr < len(image) and 0 <= nc < len(image[0]) and image[nr][nc] == old_color:
                    queue.append((nr, nc))

        return image

This code works by first checking if the starting pixel has the same color as the new color. If it does, then the function returns the image unchanged. Otherwise, the function creates a queue of the starting pixel and then enters a loop. In each iteration of the loop, the function pops the first pixel from the queue and then sets its color to the new color. The function then checks the four neighboring pixels of the popped pixel and adds them to the queue if they have the same color as the starting pixel. The loop continues until the queue is empty.

Here is a recurive solution for it:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
        m, n = len(image), len(image[0])
        original_color = image[sr][sc]

        # If the color of the start pixel is same as the new color, then return the original image.
        if original_color == color:
            return image

        def dfs(x, y):
            if x < 0 or y < 0 or x >= m or y >= n or image[x][y] != original_color:
                return

            image[x][y] = color

            dfs(x+1, y)
            dfs(x-1, y)
            dfs(x, y+1)
            dfs(x, y-1)

        dfs(sr, sc)
        return image

In this solution, the function dfs performs a depth-first search starting from the pixel (sr, sc). If the color of the pixel is not equal to the original color, the function returns immediately. Otherwise, it changes the color of the pixel and makes recursive calls for the neighboring pixels.

Q&A

What are the base cases?

In the provided solution for the Flood Fill problem, the base cases are handled inside the recursive function dfs(x, y).

There are two base cases:

  1. If the coordinates (x, y) are out of the image boundaries. That is, x < 0, y < 0, x >= m, or y >= n, where m and n are the dimensions of the image. This base case is required because we cannot perform any operation outside of the image.
  2. If the color of the pixel at coordinates (x, y) is not equal to the original color, represented by image[x][y] != original_color. This base case is needed because we only want to change the color of the pixels that have the same color as the original color.

When either of these base cases is true, the dfs function stops the current path of recursion and returns immediately.

What is the unit of work done in each recursive call?

In each recursive call, the following tasks, or “units of work”, are performed:

  1. The color of the current pixel (identified by coordinates (x, y)) is changed to the new color.

  2. The function then performs a depth-first search from the current pixel to its four neighboring pixels: up, down, left, and right. This is accomplished through the recursive calls dfs(x+1, y), dfs(x-1, y), dfs(x, y+1), and dfs(x, y-1).

This “unit of work” is applied recursively to each pixel, and through this process, all pixels connected to the starting pixel and having the same original color are discovered and their colors are changed.

Why do we have four recursive calls to dfs?

The four recursive calls in the depth-first search (dfs) method are used to explore the four possible directions from the current pixel: up, down, left, and right.

Here’s what each call represents:

  1. dfs(x+1, y): explores the pixel below the current one (moves downwards).
  2. dfs(x-1, y): explores the pixel above the current one (moves upwards).
  3. dfs(x, y+1): explores the pixel to the right of the current one.
  4. dfs(x, y-1): explores the pixel to the left of the current one.

By doing this, the algorithm ensures that all adjacent pixels that have the same original color get explored and their color gets changed. This is the standard approach in algorithms that need to explore a grid in all directions from a specific point, like the flood fill operation.

Why do we have this condition: if original_color == color: return image

This condition is checking if the original color of the pixel at the start position is the same as the new color we want to fill. If they are the same, it means we don’t need to do anything because the color we want to fill is already the color of the pixel. Therefore, we just return the original image without making any changes.

This also serves as an important base case to prevent infinite recursion. Without this check, if the original color is the same as the new color, the algorithm would keep trying to fill the same pixels over and over again because it wouldn’t detect any change in the color.

Problem Classification

This problem falls under the domain of ‘Computer Graphics’ as it deals with image manipulation through pixel values. More specifically, it uses the ‘Flood Fill’ algorithm, a concept commonly used in various applications like computer graphics for filling an area of connected pixels with a certain color.

‘What’ Components:

  1. Image: An m x n integer grid representing the pixel values of the image.
  2. Starting Pixel: The coordinates (sr, sc) of the starting pixel from which the flood fill should begin.
  3. Color: The new color with which the area defined by the flood fill algorithm should be filled.

This problem can be categorized as a ‘Graph Traversal’ problem. The reason being, the image grid can be seen as a 2D grid graph where each pixel is a node that has edges to its adjacent pixels. The task is to perform a Depth-First Search (DFS) or Breadth-First Search (BFS) starting from the given pixel until no more pixels of the same color are found. Hence, this problem leverages a classic graph traversal algorithm to solve a computer graphics-related problem.

This problem is also an example of the application of ‘Recursion’ as the flood fill algorithm inherently uses recursive calls to reach all connected nodes (or pixels, in this case). This makes the problem a good exercise for both graph traversal and recursion concepts.

Language Agnostic Coding Drills

  1. Dissect the code and identify each distinct concept it contains

The code is a Python solution for the problem of modifying a 2D grid (image) by replacing a certain color with a new color, starting from a certain pixel and spreading to all the connected pixels of the same color. The main concepts used here are:

a. Python Functions - A piece of reusable code that is used to perform a single, related action. In this code, we have two functions: `dfs` and `floodFill`.

b. Conditional Statements - The 'if' keyword is used to perform conditional operations. In this case, it is used to check whether the indices of the pixel are valid and whether the color matches the one that needs to be replaced.

c. Recursion - The dfs function calls itself within its own definition. This concept of self-calling a function is known as recursion.

d. 2D Array (Grid) Manipulation - The problem uses a 2D grid (list of lists in Python) which represents an image.

  1. List of coding concepts or drills in order of increasing difficulty

    a. Python Functions - Fundamental to Python and programming in general.

    b. Conditional Statements - Slightly more advanced than functions, as they add logic to the code.

    c. 2D Array Manipulation - This requires understanding of how to work with multidimensional data, which is more complex than working with simple variables.

    d. Recursion - It is one of the more complex concepts, especially for beginners, due to the stack mechanism involved and the potential for stack overflow if not implemented correctly.

  2. Problem-solving approach

    a. Start by identifying the pixel from which the fill should start, and what its current color is.

    b. Begin a Depth-First Search (DFS) from this pixel. If the current pixel is out of the image bounds, already filled with the new color, or its color doesn’t match the original color, we return and don’t perform any operations.

    c. If the conditions from the previous step are not met, we fill the current pixel with the new color.

    d. We then proceed to call the DFS function on the four surrounding pixels (top, bottom, left, right), treating each of them as the starting pixel for a new fill operation.

    e. After all DFS calls have been completed, we return the modified image.

This approach systematically replaces the color of the pixels, starting from the initial pixel, and spreading out to all other pixels that are connected to it and have the same original color. By doing this, it achieves the goal of performing a “flood fill” operation on the image.

Targeted Drills in Python

  1. Python coding drills for each identified concept

a. Python Functions:

1
2
3
4

def hello_world():
    print("Hello, world!")
    
hello_world()

b. Conditional Statements:

1
2
3
4
5
6
7
8

x = 10

if x > 0:
    print("x is positive")
elif x < 0:
    print("x is negative")
else:
    print("x is zero")

c. 2D Array Manipulation:

1
2
3
4

matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]

# Access element at 2nd row and 3rd column
print(matrix[1][2]) # Outputs: 6

d. Recursion:

1
2
3
4
5
6
7

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)

print(factorial(5)) # Outputs: 120
  1. Problem-specific concept

The problem-specific concept that is important for this problem is the Depth-First Search (DFS) algorithm, which is used to traverse or search through the image (2D grid).

Here’s a simple example of a DFS implementation:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def dfs(graph, node, visited):
    if node not in visited:
        visited.append(node)
        for n in graph[node]:
            dfs(graph, n, visited)
    return visited

graph = {'A': ['B', 'C'], 'B': ['D', 'E'], 'C': ['F'], 'D': [], 'E': ['F'], 'F': []}
visited = dfs(graph, 'A', [])
print(visited) # Outputs: ['A', 'B', 'D', 'E', 'F', 'C']
  1. Integration of the pieces

In the context of the initial problem:

  1. We first create the dfs function which is responsible for checking the current pixel and making the recursive calls to the adjacent pixels. This function will incorporate the concepts of Recursion, Conditional Statements and 2D Array Manipulation.

  2. Next, we define the floodFill function which initially finds the pixel’s color to be changed and then calls the dfs function. This function uses the Python Functions and Conditional Statements concepts.

  3. The floodFill function starts the whole process and uses the dfs function to recursively visit all the pixels that need to be changed. The final image is then returned with the required modifications.

By combining these components, we can create a comprehensive solution to the flood fill problem.