Welcome to OpenGenus 🎉,

Today, I will be discussing a very easy and perhaps the most beautiful algorithm that is the "Flood Fill Algorithms".

Flood Fill algorithm is an Algorithm that determines the area connected to a given node in a N-dimensional array. Some operations are performed on the connected nodes like color change. This is also known as Seed Fill Algorithm.

The idea is that you are given a N-dimensional space and some nodes are blocked with stones. One node is the source of water and unlimited water starts flowing out of it. The nodes in which the water will get into is determines by Flood Fill Algorithm.

Do you remember the MS Paint Bucket tool which we used a lot in our childhood or ever played Minesweeper game?
These all were implemented with the help of Flood Fill Algorithm!!

When applied on an image to fill a particular bounded area with color, it is also known as boundary fill.

Flood fill algorithm takes three parameters: a start node, a target node and a replacement color.

Flood Fill is an algorithm that determines and marks the connected component to which a cell belongs, in a grid. It is a Depth First Search, on a grid or a multi-dimensional array to find the component cells with the desired number. We can also use Breadth First Search!!

Remember this to avoid confusions:-

Unlike the adjacency list representation of the graph, a grid is an implicit graph which means all the cells which are adjacent to the given cell along the cartesian axes are the neighbors in the explicit graph.

Approach:-

We can use both Breadth-First-Search(BFS) and Depth-First-Search(DFS) to solve this problem.
Let's try both:-

Approach 1 (BFS) :-

Basic Steps:-

1. Create an empty queue.
2. Push the starting pixel and apply replacement color to it.
3. Now loop till the queue is empty again and pop the front node after processing it.
4. For each iteration, replace the color of the current pixel with that of the replacement.
5. Process each of the eight adjacent pixels of the current pixel and push each of the valid pixel (A valid pixel is the one which have same color as that of the current pixel).

// check if it is possible to go to pixel (x, y) from the
// current pixel. The function returns false if the pixel
// has a different color, or it's not a valid pixel
bool isValid(vector<vector<int>>& arr,int i,int j,int el){
        return !(i<0 or j<0 or i>=arr.size() or j>=arr[0].size() or el!=arr[i][j]);
}

//bfs function as follows
void bfs(int sr,int sc,int k,int ele,vector<vector<int>>& arr){
        queue<pair<int,int>> q; 
        //we are using a queue of pairs 
        q.push(make_pair(sr,sc)); 
        //push the source row and column
        while(!q.empty()){
            auto current=q.front();
            q.pop(); //after taking the front element, we pop
            //i contains x co-ordinate and j contains y co-ordinate
            int i=current.first,j=current.second;
            arr[i][j]=k;
            // process all eight adjacent pixels of the current pixel and
            if(isValid(arr,i-1,j,ele)) q.push(make_pair(i-1,j)); 
            // checking the left pixel of the current pixel and then 
            // pushing inside the queue
            if(isValid(arr,i,j-1,ele)) q.push(make_pair(i,j-1)); 
            // checking the upper pixel of the current pixel and then 
            // pushing inside the queue
            if(isValid(arr,i+1,j,ele)) q.push(make_pair(i+1,j)); 
            // checking the right pixel of the current pixel and then 
            // pushing inside the queue
            if(isValid(arr,i,j+1,ele)) q.push(make_pair(i,j+1)); 
            // checking the bottom pixel of the current pixel and 
            // then pushing inside the queue
        }
 }
 
//this is the fuction called by main
//here we had passed image, start row index(sr), start col index(sc), 
// and newPixel
vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
        if (image[sr][sc] != newColor)
            bfs(sr,sc,newColor,image[sr][sc],image);
        return image;
}

Complexity Analysis For BFS Approach

Time Complexity: O(XY)

• Here, X and Y are the number of Rows and Columns, respectively.
• In the Worst Case, each pixel may be traversed making the time complexity of the order of (XY).

Space Complexity: O(XY)

• Here, X and Y are the number of Rows and Columns, respectively.
• In the worst case, O(XY) extra space is required by the queue. Hence the overall space complexity is O(XY).

Approach 2 (DFS)

Basic Steps:-

1. Apart from BFS, we can also use DFS to solve this problem.
2. The main idea of Depth First Search is to start from a source node in the matrix, replace its color and then recursively explore all the valid four adjacents nodes (or pixels) and replace their color too!!

// check if it is possible to go to pixel (x, y) from the
// current pixel. The function dont do a dfs if the pixel
// has a different color, or it's not a valid pixel

void dfs(int i,int j,int k,int ele,vector<vector<int>>& arr){
        if(i<0 or j<0 or i>=arr.size() or j>=arr[0].size() or arr[i][j]!=ele) return;
        arr[i][j]=k;
        dfs(i-1,j,k,ele,arr); // dfs on left pixel
        dfs(i,j-1,k,ele,arr); // dfs on upper pixel
        dfs(i+1,j,k,ele,arr); // dfs on right pixel
        dfs(i,j+1,k,ele,arr); // dfs on bottom pixel
}
 
//this is the fuction called by main
//here we have passed image, start row index(sr), start col index(sc), and newPixel
vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
        if (image[sr][sc] != newColor)
            dfs(sr,sc,newColor,image[sr][sc],image);
        return image;
}

Complexity Analysis For DFS Approach:-

Time Complexity: O(XY)

• Here, M and N are the numbers of rows and columns, respectively.
• It will be proportional to the number of pixels in the filled area. So, at max XY pixels can be traversed. Thus the time complexity is O(XY).

Space Complexity: O(XY)

• Here, X and Y are the number of Rows and Columns, respectively.
• In the worst case, O(XY) extra space is required by the recursion auxillary stack. Hence the overall space complexity is O(XY).

With this article at OpenGenus, you must have the complete idea of Flood Fill Algorithms.