Solution For Flood Fill

The Flood Fill problem on LeetCode is a classic problem in computer graphics. The problem involves filling in a region of an image with a given color. In this article, we will explain the problem and provide a detailed solution.

Problem Statement:

Given an image represented by a 2D integer array, and the location of a pixel (x, y) in the image, you need to change the color of the pixel to a new color newColor, and then recursively fill the neighboring pixels of the same old color to the new color until all the pixels in the region are filled with the new color.

Solution:

The problem can be solved using Depth First Search (DFS) or Breadth First Search (BFS). We will use DFS to solve this problem.

Step 1: Check the base case:

If the source pixel (x, y) has already been filled with the new color or if the source pixel is not of the old color, then we do not need to fill the region and we can return the image as is.

Step 2: Update the source pixel:

Change the color of the source pixel (x, y) to the new color newColor.

Step 3: Recursive Flood Fill:

We can now recursively fill the neighboring pixels of the same old color to the new color using DFS.

Consider the current pixel (x, y) in the image. We can check its neighboring pixels to see if they need to be filled or not. We only need to check the pixels that are within the bounds of the image and are of the old color. To ensure that we check each and every pixel in the region, we will perform the DFS in all four directions – top, right, bottom, and left.

We will use a recursive function for the DFS. The function will take the image, the coordinates of the current pixel (x, y), the old color, and the new color as inputs. We will also use an auxiliary function to check if a pixel is within the bounds of the image.

Here is the algorithm for the Flood Fill problem using DFS:

1. Create a function called ‘FloodFill’ that takes the image, the coordinates of the current pixel (x, y), the old color, and the new color as inputs.

2. Check the base case:

a. If the pixel (x, y) is out of bounds or has already been filled with the new color or is not of the old color, return the image.

1. Update the source pixel (x, y) to the new color newColor.

2. Recursively fill the neighboring pixels of the same old color to the new color using DFS:

a. Call the FloodFill function on the pixel to the top of (x, y).
b. Call the FloodFill function on the pixel to the right of (x, y).
c. Call the FloodFill function on the pixel to the bottom of (x, y).
d. Call the FloodFill function on the pixel to the left of (x, y).

1. Return the image.

Here is the Python code for the Flood Fill problem using DFS:

“`
def FloodFill(image, x, y, oldColor, newColor):
# check if the pixel is out of bounds or has already been filled with new color
if (not withinBounds(image, x, y)) or image[x][y] == newColor or image[x][y] != oldColor:
return image

# update the source pixel to new color
image[x][y] = newColor

# recursively fill the neighboring pixels of the same old color to the new color using DFS
FloodFill(image, x-1, y, oldColor, newColor)  # top
FloodFill(image, x, y+1, oldColor, newColor)  # right
FloodFill(image, x+1, y, oldColor, newColor)  # bottom
FloodFill(image, x, y-1, oldColor, newColor)  # left

return image

def withinBounds(image, x, y):
# check if the pixel is within the bounds of the image
if x < 0 or x >= len(image) or y < 0 or y >= len(image[0]):
return False
return True
“`

Time and Space Complexity:

The time complexity of the algorithm is O(m * n) where m and n are the dimensions of the image. This is because we visit each pixel in the image only once.

The space complexity of the algorithm is O(m * n) where m and n are the dimensions of the image. This is because we use a recursive function and each call to the function creates a new stack frame which takes up memory. In the worst case, all the pixels in the image can be part of the same region and we will need to create a stack frame for each pixel.

Step by Step Implementation For Flood Fill

There are a couple of different ways to approach this problem. One way would be to use a breadth-first search algorithm, and another would be to use a depth-first search algorithm.

We'll start by looking at the breadth-first search algorithm. The basic idea is to keep a queue of points that need to be visited, and then visit each point in the queue in turn. We can keep track of which points have been visited using a boolean array.

We'll start by putting the starting point in the queue. Then, while the queue is not empty, we'll take the first point off of the queue and look at its four neighbors. If any of the neighbors have not been visited and are not part of the image, we'll add them to the queue.

Once we've visited all of the points in the queue, we're done.

Here's some pseudocode for the algorithm:

queue = [starting point]

visited = new boolean array of size of image

visited[starting point] = true

while queue is not empty:

current = queue.remove()

for each neighbor of current:

if neighbor is not visited and is not part of the image:

queue.add(neighbor)

visited[neighbor] = true

Now let's look at the depth-first search algorithm. The basic idea is similar to the breadth-first search algorithm, but instead of using a queue, we'll use a stack.

As before, we'll start by putting the starting point on the stack. Then, while the stack is not empty, we'll take the top point off of the stack and look at its four neighbors. If any of the neighbors have not been visited and are not part of the image, we'll add them to the stack.

Once we've visited all of the points in the stack, we're done.

Here's some pseudocode for the algorithm:

stack = [starting point]

visited = new boolean array of size of image

visited[starting point] = true

while stack is not empty:

current = stack.pop()

for each neighbor of current:

if neighbor is not visited and is not part of the image:

stack.push(neighbor)

visited[neighbor] = true

def floodFill(image, sr, sc, newColor):
    
    # Base case: If the current pixel is the same color as the new color, then there's
    # nothing to do.
    if image[sr][sc] == newColor:
        return image
    
    # Get the dimensions of the image.
    rows, cols = len(image), len(image[0])
    
    # Perform a depth-first search to find all connected pixels of the
    # current pixel's color.
    color = image[sr][sc]
    image[sr][sc] = newColor
    if sr - 1 >= 0 and image[sr - 1][sc] == color:
        image = floodFill(image, sr - 1, sc, newColor)
    if sr + 1 < rows and image[sr + 1][sc] == color:
        image = floodFill(image, sr + 1, sc, newColor)
    if sc - 1 >= 0 and image[sr][sc - 1] == color:
        image = floodFill(image, sr, sc - 1, newColor)
    if sc + 1 < cols and image[sr][sc + 1] == color:
        image = floodFill(image, sr, sc + 1, newColor)
    return image

var floodFill = function(image, sr, sc, newColor) {
    // create a variable to store the starting color
    // this variable will help us keep track of which pixels have been visited
    let startingColor = image[sr][sc];
    
    // create a helper function that takes in the current row, column, and color
    // this function will recursively call itself on any adjacent pixels with the same color
    function fill(row, column, color) {
        // if the row or column is out of bounds, or the current pixel is a different color, return
        if (row < 0 || row >= image.length || column < 0 || column >= image[0].length || image[row][column] !== color) {
            return;
        }
        // set the current pixel's color to the new color
        image[row][column] = newColor;
        // recursively call fill on the pixel above
        fill(row - 1, column, color);
        // recursively call fill on the pixel to the right
        fill(row, column + 1, color);
        // recursively call fill on the pixel below
        fill(row + 1, column, color);
        // recursively call fill on the pixel to the left
        fill(row, column - 1, color);
    }
    
    // call the helper function
    fill(sr, sc, startingColor);
    
    // return the updated image
    return image;
};

class Solution {
public:
    vector> floodFill(vector>& image, int sr, int sc, int newColor) {
        
        // if newColor is same as starting color then return the image
        if(image[sr][sc] == newColor)
            return image;
        
        // set the starting color to newColor
        image[sr][sc] = newColor;
        
        // check for all 4 directions
        if(sr+1 < image.size() && image[sr+1][sc] != newColor)
            floodFill(image, sr+1, sc, newColor);
        if(sr-1 >= 0 && image[sr-1][sc] != newColor)
            floodFill(image, sr-1, sc, newColor);
        if(sc+1 < image[0].size() && image[sr][sc+1] != newColor)
            floodFill(image, sr, sc+1, newColor);
        if(sc-1 >= 0 && image[sr][sc-1] != newColor)
            floodFill(image, sr, sc-1, newColor);
        
        // return the updated image
        return image;
    }
};

using System; 
  
class GFG { 
      
// DFS function 
static void floodFillUtil(int[,] screen, int x, int y, 
                                int prevC, int newC) 
{ 
    // Base cases 
    if (x < 0 || x >= screen.GetLength(0) || 
        y < 0 || y >= screen.GetLength(1)) 
        return; 
    if (screen[x, y] != prevC) 
        return; 
  
    // Replace the color at (x, y) 
    screen[x, y] = newC; 
  
    // Recur for north, east, south and west 
    floodFillUtil(screen, x + 1, y, prevC, newC); 
    floodFillUtil(screen, x - 1, y, prevC, newC); 
    floodFillUtil(screen, x, y + 1, prevC, newC); 
    floodFillUtil(screen, x, y - 1, prevC, newC); 
} 
  
// It mainly finds the previous color on (x, y) and 
// calls floodFillUtil() 
static void floodFill(int[,] screen, int x, int y, int newC) 
{ 
    int prevC = screen[x, y]; 
    floodFillUtil(screen, x, y, prevC, newC); 
} 
  
/* A utility function to print screen[M][N] */
static void printScreen(int[,] screen) 
{ 
    for (int i = 0; i < screen.GetLength(0); i++) 
    { 
        for (int j = 0; j < screen.GetLength(1); j++) 
            Console.Write(screen[i, j] + " "); 
        Console.WriteLine(); 
    } 
} 
  
// Driver code 
public static void Main() 
{ 
    int[,] screen = {{1, 1, 1, 1, 1, 1, 1, 1}, 
                     {1, 1, 1, 1, 1, 1, 0, 0}, 
                     {1, 0, 0, 1, 1, 0, 1, 1}, 
                     {1, 2, 2, 2, 2, 0, 1, 0}, 
                     {1, 1, 1, 2, 2, 0, 1, 0}, 
                     {1, 1, 1, 2, 2, 2, 2, 0}, 
                     {1, 1, 1, 1, 1, 2, 1, 1}, 
                     {1, 1, 1, 1, 1, 2, 2, 1}, 
                    }; 
    int x = 4, y = 4, newC = 3; 
    floodFill(screen, x, y, newC); 
  
    Console.Write("Updated screen "
         + "after call to floodFill: \n"); 
    printScreen(screen); 
} 
} 
  
// This code is contributed by 29AjayKumar