Flood Fill Algorithm

Difficulty: Medium, Asked-In: Amazon, Microsoft, Adobe.

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

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

Our goal is to replace the colour of all pixels connected to the starting pixel (x, y) in the four cardinal directions (up, down, left, right) with the new colour, as well as any pixels connected to those pixels, and so on. Once the flood fill algorithm is complete, we need to return the modified image.

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 colour and paint them with a new colour. To do this, we begin at a specified starting point (x, y) and paint it with the new colour. 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 colour as the original.

If they do, we also paint them with the new colour and repeat this process recursively for their surrounding points. This continues until all the connected points of the original colour have been painted with the new colour.

Solution steps

1. We define a function floodFill that takes an image, a starting point (x, y), and a new colour to be filled as the input.
2. Inside the function, we first check if the starting point already has the same colour as the new colour. If it does, then there is no need to perform the flood fill operation.
3. Otherwise, we call a helper function floodFillHelper 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.
4. 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 floodFillHelper 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.
5. if (x >= 1), floodFillHelper (image, x - 1, y, color, newColor).
6. if (y >= 1), floodFillHelper (image, x, y - 1, color, newColor).
7. if (x + 1 < m), floodFillHelper (image, x + 1, y, color, newColor).
8. 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.

Implementation 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;
}

Implementation code Python

def floodFillHelper(image, x, y, color, newColor):
    m = len(image)
    n = len(image[0])

    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)


def floodFill(image, x, y, newColor):
    color = image[x][y]
    if color != newColor:
        floodFillHelper(image, x, y, color, newColor)
    return image

Implementation code Java

public class FloodFill 
{
    private void floodFillHelper(int[][] image, int x, int y, int color, int newColor) 
    {
        int m = image.length;
        int n = image[0].length;

        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);
        }
    }

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

Time and space complexity 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 and steps

The above idea of flood fill algorithm using DFS is tail recursive i.e. the recursive calls are the last instruction in the algorithm. So we can easily implement it iteratively using the stack.

1. We push the starting point (x, y) onto the stack. Note: Here we push both coordinates of a point as a pair.
2. Then, we run a loop until the stack is empty.
3. At each iteration of the loop, we pop a point from the stack. If the point has the same colour as the starting point (x, y), we colour it with the new colour and push any surrounding points onto the stack.
4. By the end of the loop, all points in the connected region will have been coloured with the new colour.

Implementation 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;
}

Implementation code Python

def floodFill(image, x, y, newColor):
    if image[x][y] == newColor:
        return image
    
    m = len(image)
    n = len(image[0])

    temp = image[x][y]
    stack = [(x, y)]

    while stack:
        i, j = stack.pop()

        if image[i][j] == temp:
            image[i][j] = newColor

            if i + 1 < m:
                stack.append((i + 1, j))

            if i - 1 >= 0:
                stack.append((i - 1, j))

            if j + 1 < n:
                stack.append((i, j + 1))

            if j - 1 >= 0:
                stack.append((i, j - 1))

    return image

Implementation code Java

public class FloodFillAlgorithm
{
    public int[][] floodFill(int[][] image, int x, int y, int newColor) 
    {
        if (image[x][y] == newColor) 
            return image;
            
        int m = image.length;
        int n = image[0].length;

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

        while (!stack.empty()) 
        {
            int[] curr = stack.pop();
            int i = curr[0];
            int j = curr[1];

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

                if (i + 1 < m)
                    stack.push(new int[]{i + 1, j});

                if (i - 1 >= 0)
                    stack.push(new int[]{i - 1, j});

                if (j + 1 < n)
                    stack.push(new int[]{i, j + 1});

                if (j - 1 >= 0)
                    stack.push(new int[]{i, j - 1});
            }
        }

        return image;
    }
}

Time and space complexity 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, we can also use the breadth-first search (BFS) to visit points in the image and colour the connected region of points. For this, we initialize a queue to store the points that need to be visited and push the starting point into it. Before starting the loop, we also save the original colour of the starting point in a variable.

Now, we run a loop for BFS traversal where we continuously remove points from the front of the queue and colour them with the new colour. For each point, we also push the four neighbouring points (top, bottom, left, and right) into the queue if they are within the bounds of the image. We continue this process until the queue is empty.

Solution steps

Step 1: First, we check if the starting pixel already has the newColor. If it does, we return the image without making any changes.

Step 2: Now, we create a queue of pairs of integers to store the pixels that need to be visited during the algorithm.

Step 3: We also store the original colour of the starting pixel in the variable orginalColor and define an array of integers called offsets [-1, 0, 1, 0, -1]. We use this array 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])

Step 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 colour with the newColor.
• Now we iterate through the offsets[] array 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.

Step 5: When the queue is empty, we have visited all reachable pixels with the original colour and we return the modified image.

Implementation 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;
}

Implementation code Python

def floodFill(image, x, y, newColor):
    if image[x][y] == newColor:
        return image
        
    m = len(image)
    n = len(image[0])
    
    q = deque()
    q.append((x, y))
    
    originalColor = image[x][y]
    offsets = [-1, 0, 1, 0, -1]
    
    while q:
        p = q.popleft()
        image[p[0]][p[1]] = newColor
        
        for i in range(len(offsets) - 1):
            if (0 <= p[0] + offsets[i] < m and
                0 <= p[1] + offsets[i + 1] < n and
                image[p[0] + offsets[i]][p[1] + offsets[i + 1]] == originalColor):
                
                q.append((p[0] + offsets[i], p[1] + offsets[i + 1]))
    
    return image

Implementation code Java

public class FloodFill 
{
    public int[][] floodFill(int[][] image, int x, int y, int newColor) 
    {
        if (image[x][y] == newColor)
            return image;
        
        int m = image.length;
        int n = image[0].length;
        
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{x, y});
        
        int originalColor = image[x][y];
        int[] offsets = {-1, 0, 1, 0, -1};
        
        while (queue.isEmpty() == false) 
        {
            int[] p = queue.poll();
            image[p[0]][p[1]] = newColor;
            
            for (int i = 0; i < offsets.length - 1; i = i + 1) 
            {
                int newX = p[0] + offsets[i];
                int newY = p[1] + offsets[i + 1];
                
                if (newX >= 0 && newX < m &&
                    newY >= 0 && newY < n &&
                    image[newX][newY] == originalColor) 
                {
                    
                    queue.offer(new int[]{newX, newY});
                }
            }
        }
        
        return image;
    }
}

Time and space complexity analysis

The time complexity of this implementation is O(mn). 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) because 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

We use the flood fill algorithm in many areas of computer science: image processing, computer graphics, game development, etc.

• Image editing software: We can use the flood fill algorithm to fill an area of an image with a new colour, just like the "paint bucket" tool in image editors. We can also use it to remove a specific colour from an image, replace a colour with transparency, and perform other colour adjustments.
• Computer graphics: We often use the flood fill algorithm for collision detection in 2D games. By flood-filling the area around an object, the flood-fill algorithm can quickly determine if the object is touching a wall or another object. Additionally, we can also use it for creating mazes, cave systems, and other procedural-generated game content.
• Robotics: We can apply the flood fill algorithm to implement a robot vacuum cleaner or autonomous robot. When a robot explores the environment, it needs to make a map of it, and the flood Fill algorithm can help us to find the unknown area.

One of the main advantages of the flood fill algorithm is its simplicity and speed. We can implement it in just a few lines of code, which can quickly fill large areas of an image or game environment. But this algorithm can be affected by memory limits or a large number of connected areas, and performance may become an issue.

Similar coding questions to explore and solve

Number of Islands: Given a 2D grid of 1s and 0s, where 1 represents land and 0 represents water, count the number of islands in the grid. An island is a group of connected 1s, where a connection is defined as being adjacent horizontally or vertically (not diagonally).

Surrounded Regions: Given a 2D grid of characters, where 'X' represents an obstacle and 'O' represents an open space, identify all the regions that are surrounded by 'X' characters and replace them with 'X'. A region is considered surrounded if it is not connected to any open space on the grid.

Knight's Shortest Path: You are given a chessboard and a starting position for a knight piece. Your task is to find the shortest path for the knight to reach a given destination on the chessboard. The knight moves in an L-shaped pattern, two spaces horizontally and one space vertically, or two spaces vertically and one space horizontally.

Shortest Distance in a Grid with Obstacles: You are given a 2D grid of integers, where some cells contain obstacles and cannot be passed through. Your task is to find the shortest distance between two points in the grid.

Unique Paths: You are given a 2D grid of integers, where 1 represents a block that you cannot pass through and 0 represents an open space that you can pass through. Your task is to count the number of unique paths from the top-left corner to the bottom-right corner of the grid.

Maze: You are given a 2D grid of characters, where 'S' represents the start point, 'E' represents the end point, and '#' represents a wall that you cannot pass through. Your task is to find a path through the maze from the start point to the end point.

Enjoy learning, enjoy coding, enjoy algorithms!