Flood Fill Algorithm

Difficulty: Medium, Asked-In: Amazon, Microsoft

Key takeaway: An excellent problem to learn problem-solving using iterative (BFS) and recursive (DFS) approaches.

Let’s understand the problem

The flood fill problem is a way to fill a region of connected pixels with a new colour, starting from a given pixel in an image. Here an image is represented by a grid of pixels and each pixel is represented by an integer value.

Problem statement

You are given an image represented by an m x n grid of integers, where image[i][j] represents the pixel value at position (i, j). You are also given the coordinates of a starting pixel (x, y) and a new color to use for the flood fill operation.

The goal is to replace the color of all pixels connected to the starting pixel in the four cardinal directions (up, down, left, right) with the new color, as well as any pixels connected to those pixels, and so on. Once the flood fill is complete, you should return the modified image.

Flood fill algorithm example

Discussed solution approaches

Solution approach using DFS traversal (Recursive backtracking)
Solution approach using stack (Iterative backtracking)
Solution approach using BFS traversal

Solution approach using DFS traversal (Recursive backtracking)

Solution idea

One idea is to explore all the regions connected to a given color and paint them with a new color. To do this, we begin at a specified starting point (x, y) and paint it with the new color. We then check the surrounding points (x, y + 1), (x - 1, y), (x + 1, y), and (x, y - 1) to ensure that they are valid and have the same color as the original. If they do, we also paint them with the new color and repeat this process recursively for their surrounding points. This continues until all the connected points of the original color have been painted with the new color.

Solution steps

We define a function called floodFill that takes an image, a starting point (x, y), and a new colour to be filled. Inside the function, we first check if the starting point already has the same colour as the new colour. If it does, there is no need to perform the flood fill. Otherwise, we call the floodFillHelper function to fill the connected region with the new colour. FloodFillHelper is a recursive function that takes an image, a current point (x, y), the original colour, and the new colour.

Inside floodFillHelper, we check if the current point (x, y) has the same colour as the original colour. If it does, we change the colour of the current point to the new colour, and call the function recursively on the four neighbouring points: (x, y + 1), (x - 1, y), (x + 1, y), and (x, y - 1). We also ensure that these points are within the bounds of the image and have the same colour as the original.

if (x >= 1), floodFillHelper (image, x - 1, y, color, newColor)
if (y >= 1), floodFillHelper (image, x, y - 1, color, newColor)
if (x + 1 < m), floodFillHelper (image, x + 1, y, color, newColor)
if (y + 1 < n), floodFillHelper(image, x, y + 1, color, newColor)

This process continues until all connected points with the original color have been colored with the new color.

Solution code C++

void floodFillHelper(std::vector<std::vector<int>>& image, int x, int y, int color, int newColor) 
{
    int m = image.size();
    int n = image[0].size();
    
    if (image[x][y] == color) 
    {
        image[x][y] = newColor;
        
        if (x >= 1) 
            floodFillHelper(image, x - 1, y, color, newColor);
        
        if (y >= 1) 
            floodFillHelper(image, x, y - 1, color, newColor);
        
        if (x + 1 < m) 
            floodFillHelper(image, x + 1, y, color, newColor);
        
        if (y + 1 < n) 
            floodFillHelper(image, x, y + 1, color, newColor);
    }
}

vector<vector<int>> floodFill(vector<vector<int>>& image, int x, int y, int newColor) 
{
    int color = image[x][y];
    if (color != newColor) 
        floodFillHelper(image, x, y, color, newColor);
    return image;
}

Solution analysis

The time complexity of this code is O(m*n), where m and n are the dimensions of the image. This is because the worst-case time complexity occurs when we need to visit and update every pixel in the image.

The space complexity of this code is O(m*n). This is because in the worst case, the recursion stack will maintain a frame for every pixel in the image.

Solution approach using stack (Iterative backtracking)

Solution idea

The flood fill algorithm using DFS, as shown above, is tail recursive. This means that the recursive calls are the last instruction in the algorithm, thus it can be easily implemented iteratively by using the stack data structure.

To begin, we push the starting point (x, y) onto the stack. Then, we run a loop until the stack is empty. In each iteration of the loop, we pop a point from the stack. If the point has the same color as the starting point (x, y), we color it with the new color, and push any surrounding points onto the stack. By the end of this process, all points in the connected region will have been colored.

Solution code C++

vector<vector<int>> floodFill(vector<vector<int>>& image, 
                                  int x, int y, int newColor)
{
    if (image[x][y] == newColor)
        return image;
    
    int m = image.size();
    int n = image[0].size();    

    int temp = image[x][y];
    stack<pair<int, int>> stack;
    stack.push({x, y});

    while (stack.empty() == false)
    {
        int i = stack.top().first, 
        int j = stack.top().second;
        stack.pop();

        if (image[i][j] == temp)
        {
            image[i][j] = newColor;

            if (i + 1 < m)
                stack.push({i + 1, j});
            
            if (i - 1 >= 0)
                stack.push({i - 1, j});
            
            if (j + 1 < n)
                stack.push({i, j + 1});
            
            if (j - 1 >= 0)
                stack.push({i, j - 1});
        }
    }

    return image;
}

Solution analysis

The time complexity of this implementation is O(mn) in the worst case because, in the worst case, we need to visit each point in the image at most once. Similarly, the space complexity is also O(mn) in the worst case, as we need to store all m * n points on the stack in the worst case.

Solution approach using BFS traversal

Solution idea

Just like DFS traversal, the breadth-first search (BFS) algorithm can also be used to visit points in the image and color the connected region of points starting from (x, y). To accomplish this, we initialize a queue to hold the points that need to be visited and push the starting point into it. Before entering the loop, we also save the original color of the starting point in a variable.

Now, we run a loop for BFS traversal where we continuously pop points from the front of the queue and color them with the new color. For each point, we also push the four neighboring points (top, bottom, left, and right) into the queue if they are within the bounds of the image and have the same color as the original. This process continues until the queue is empty.

Solution steps

The floodFill() function takes four parameters: a reference to a 2D matrix of integers representing the image, the row and column indices of the starting pixel (x, y), and the newColor.

First, we check if the starting pixel already has the newColor. If it does, we return the image without making any changes.
Now, we create a queue of pairs of integers to store the pixels that need to be visited during the algorithm.
We also store the original color of the starting pixel in the variable orginalColor and define a vector of integers called offsets {-1, 0, 1, 0, -1} which will be used to traverse the image in the four cardinal directions. All surrounding points of point (x, y) are:
- (x - 1, y): (x + offsets[0], y + offset[1])
- (x, y + 1): (x + offsets[1], y + offset[2])
- (x + 1, y): (x + offsets[2], y + offset[3])
- (x, y - 1): (x + offsets[3], y + offset[4])
Now, we run a loop until the queue is empty.
- At the start of each iteration, we remove the front element of the queue and replace its color with the newColor.
- We iterate through the offsets vector and check the four cardinal directions around the current pixel.
- If the pixel in that direction has the originalColor and is within the bounds of the image, we add it to the queue for processing in future iterations.
When the queue is empty, all reachable pixels with the original color have been visited and we return the modified image.

Solution code C++

vector<vector<int>> floodFill(vector<vector<int>>& image, int x, int y, int newColor) 
{     
    if (image[x][y] == newColor) 
        return image;
        
    int m = image.size(), 
    int n = image[0].size();
    
    queue<pair<int, int>> q;       
    q.push(make_pair(x, y));
    
    int orginalColor = image[x][y];
    vector<int> offsets = {-1, 0, 1, 0, -1};
    
    while(q.size()) 
    {
        pair<int, int> p = q.front();
        q.pop();
        image[p.first][p.second] = newColor; 
        
        for (int i = 0; i < offsets.size() - 1; i = i + 1) 
        {
            if(p.first + offsets[i] >= 0      // within upper bound 
               && p.first + offsets[i] < m    // within lower bound
               && p.second + offsets[i + 1] >= 0  // within left bound
               && p.second + offsets[i + 1] < n  // within right bound
               && image[p.first + offsets[i]][p.second + offsets[i + 1]] == orginalColor)
            {   
                q.push(make_pair(p.first + offsets[i], p.second + offsets[i+1]));
            }    
        }
    }
        
    return image;
}

Solution analysis

The time complexity of this implementation is O(mn) in the worst case because, in the worst case, BFS traversal needs to visit each point in the image at most once. Similarly, the space complexity is also O(mn) in the worst case, as we need to store all m * n points on the queue in the worst case.

Critical ideas to think!

Can we consider implementing a BFS approach without using an offset[] array? How might we implement it using a series of if and else statements?
What are the best and worst case inputs for all of the above solutions?
The worst case time and space complexity of all of the above approaches are the same. Which one is more efficient in terms of performance?
Can we further optimize the above approaches in terms of space and time complexity?
Is there an approach to solving the flood fill problem using constant extra space?

Application of Flood fill algorithm in computer science

The Flood Fill algorithm is used in many areas of computer science, including image processing, computer graphics, and game development.

Image editing software: Flood fill algorithm is used to fill an area of an image with a new color, similar to the "paint bucket" tool in many image editors. It can also be used to remove a specific color from an image, replace a color with transparency, and perform other color adjustments.
Computer graphics: Flood Fill algorithm is often used for collision detection in 2D games. By flood-filling the area around an object, the algorithm can quickly determine if the object is touching a wall or another object. Additionally, it can also be used for creating mazes, cave systems, and other procedural-generated game content.
Robotics: The Flood Fill algorithm can also be applied in the robot vacuum cleaner or autonomous robot. when robot explores the environment, it needs to make a map of it, and Flood Fill algorithm can help to find the unknown area.

One of the main advantages of the Flood Fill algorithm is its simplicity and speed. It can be implemented in just a few lines of code and can quickly fill large areas of an image or game environment. However, the algorithm can be affected by memory limits or the large number of connected areas, and performance may become an issue.

Flood Fill Algorithm

Let’s understand the problem

Problem statement

Discussed solution approaches

Solution approach using DFS traversal (Recursive backtracking)

Solution idea

Solution steps

Solution code C++

Solution analysis

Solution approach using stack (Iterative backtracking)

Solution idea

Solution code C++

Solution analysis

Solution approach using BFS traversal

Solution idea

Solution steps

Solution code C++

Solution analysis

Critical ideas to think!

Application of Flood fill algorithm in computer science

Similar coding questions to explore and solve

More From EnjoyAlgorithms