Introduction
Today’s problem, i.e., –“Flood fill Algorithm”, is highly asked in product-based companies like Amazon, Google and Microsoft.
We’ll go over all the methods, including brute force and the most efficient way to solve this problem.
Without further ado, let’s get started with the problem statement.
Problem Statement For Flood Fill Algorithm
You are given a 2D screen arr[][] where each arr[i][j] is an integer representing the colour of that pixel, also given the location of a pixel (X, Y) and a new colour C. Your task is to replace the colour of the given pixel and all adjacent same-coloured pixels with the new colour.
Note: Here the Adjacent positions are (left ,right,down,up) i.e. (x-1,y), (x+1,y), (x,y+1) and (x,y-1) respectively.
Let’s see the below example to understand the problem statement better:
- Given array is a 2-D array of order (3*3), and the location of the pixel provided is (1,1).
- The pixel’s colour is ‘1,’ and the new colour to be changed is ‘2.
Wondering how to get the solution?
Come let’s discuss it-
1. Note the pixel location; its colour is ‘1,’ and the new colour to be changed is ‘2.’2. So, first, change the colour of the pixel at location (1,1).3. Now, check the adjacent locations with the same colour and replace them with ‘2.’4. So, following this procedure the colour of pixels at locations (0,0), (0,1), (0,2), (1,0), (1,1), (2,0) will be changed. |
You might wonder why the colour of the pixel at location (2,2) is not changed?
- The reason is that location (2,2) is not adjacent to the provided location by any means so, it will not be changed.
If the idea behind solving the problem is clear, let’s head on to the methods to solve the “Flood fill Algorithm” problem.
Method 1: Brute force (Using Recursion)
Here, the idea will be that we will first replace the colour of a given pixel’s location and then call the function recursively to change all the adjacent pixels with the same colour.
Algorithm For Brute Force
- Let us assume that the position of the pixel is given as (x,y).
- If any of ‘x’ or ‘y’ is outside the screen, simply return.
- Also, if the screen colour at location (x,y) is the same as the provided colour (in this case, the provided colour is 2), then return.
- Else, change the colour of the given location pixel and call the function recursively for its adjacent positions (left ,right,down,up) i.e. on (x-1,y), (x+1,y), (x,y+1) and (x,y-1) respectively.
- Remember diagonal positions are not adjacent.
Below, C++ code is given for your better understanding:
Code for Brute Force
#include<iostream> using namespace std; //make the dimensions as you wish #define M 3 #define N 3 void floodFillAlgo(int arr[M][N], int x, int y, int preColor, int newColor) { // if x or y is out of the screen if (x < 0 || x >= M || y < 0 || y >= N) return; //if the colour already at position is not the same as the previous colour if (arr[x][y] != preColor) return; //if the colour is already the same as the new colour if (arr[x][y] == newColor) return; // Replace the colour at (x, y) arr[x][y] = newColor; //Call the function recursively for the adjacent positions floodFillAlgo(arr, x+1, y, preColor, newColor); floodFillAlgo(arr, x-1, y, preColor, newColor); floodFillAlgo(arr, x, y+1, preColor, newColor); floodFillAlgo(arr, x, y-1, preColor, newColor); } //Function to know what the previous colour was void Fill(int arr[M][N], int x, int y, int newColor) { int preColor = arr[x][y]; //check if the previous colour is not the same as the new colour if(preColor==newColor) return; //if the colour asked is different floodFillAlgo(arr, x, y, preColor, newColor); } int main() { int arr[M][N] = {{1, 1, 1}, {1, 1, 0}, {1, 0, 1},}; int x = 1, y = 1, newColor = 2; Fill(arr, x, y, newColor); cout <<“The screen after implementing the Flood fill algo will be: \n”; for (int i=0; i<M; i++) { for (int j=0; j<N; j++) cout << arr[i][j] << ” “; cout << endl; } } |
Output
The screen after implementing the Flood fill Algo will be: 2 2 2 2 2 0 2 0 1
Complexity Analysis for Brute Force
Time Complexity: O(M*N)
- It will be proportional to the number of pixels in the filled area. So, at max M*N pixels can be traversed. Here, M and N are the numbers of rows and columns, respectively.
- Thus, the complexity will be O(M*N).
Space Complexity: O(M*N)
- Here, M and N are the numbers of rows and columns respectively.
- In the worst case, O(M * N) extra space is required by the recursion stack. Hence the overall space complexity is O(M * N).
Method 2: Using the BFS approach
Here in this method to implement the Flood fill algorithm, we will use the idea of “Breadth-First Search.”
Algorithm For BFS Approach
- Create a queue that will have pairs
- Create a Matrix (Visit[M][N])
- Insert the provided location as the initial index into the queue.
- Now, mark the initial index as visited in a newly created Visit Matrix.
- While the queue is not empty, follow the below steps-
- Pop-out the first element from the queue
- Store this value as this would act like the previous colour of the pixel at that location
- Now change the colour of the index that is being popped out from the queue
- Check for its all possible adjacent indexes (x,y+1), (x,y-1), (x+1,y) and (x-1,y) whether they exist or not
- If yes, then check the colour at that index, and it should be equal to the previous colour since it is not changed, so its value in the Visited Matrix should be ‘0’ as it is not visited yet.
- Now, if all steps are true, push the index or location into the queue and mark its corresponding position in the Visited Matrix as ‘1’.
- Print out the matrix after the above implementation for the flood fill algorithm.
Below is the C++ code for your better understanding:
Code for BFS Approach
#include <bits/stdc++.h> using namespace std; //check if the coordinate is valid or not int checkCoord(int x, int y, int N, int M) { if (x < 0 || y < 0) { return 0; } if (x >= N || y >= M) { return 0; } return 1; } //Using BFS to implement flood fill algo void BFS(int N, int M, int arr[3][3], int x, int y, int newcolour) { //array to mark visited and non visited by 1 and 0 respectively int visit[100][100]; // Initialing all to zero means non visited memset(visit, 0, sizeof(visit)); // Creating queue for bfs queue<pair<int, int> > q; // Pushing the given index as (x, y) q.push({ x, y }); // Mark (x, y) as visited visit[x][y] = 1; // Until queue is not empty while (q.empty() != 1) {//taking out queue front pair<int, int> coor = q.front(); int x = coor.first; int y = coor.second; int preColor = arr[x][y]; //changing the colour to newcolour arr[x][y] = newcolour; // Poping front pair of queue q.pop(); // check for upper pixel if (checkCoord(x + 1, y, N, M) && visit[x + 1][y] == 0 && arr[x + 1][y] == preColor) { q.push({ x + 1, y }); visit[x + 1][y] = 1; } // check for down pixel if (checkCoord(x – 1, y, N, M) && visit[x – 1][y] == 0 && arr[x – 1][y] == preColor) { q.push({ x – 1, y }); visit[x – 1][y] = 1; } //check for Right side pixel if (checkCoord(x, y + 1, N, M) && visit[x][y + 1] == 0 && arr[x][y + 1] == preColor) { q.push({ x, y + 1 }); visit[x][y + 1] = 1; } //check for Left side Pixel if (checkCoord(x, y – 1, N, M) && visit[x][y – 1] == 0 && arr[x][y – 1] == preColor) { q.push({ x, y – 1 }); visit[x][y – 1] = 1; } } //print the final matrix after change cout<<“Final screen after implementing flood fill algo will be:”<<endl; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { cout << arr[i][j] << ” “; } cout << endl; } cout << endl; } int main() { int N, M, x, y, newcolour; N = 3; M = 3; int arr[3][3] = {{1, 1, 1}, {1, 1, 0}, {1, 0, 1}, }; x = 1, y = 1, newcolour = 3; BFS(N, M, arr, x, y, newcolour); return 0; } |
Output:
Final screen after implementing flood fill algo will be: 3 3 3 3 3 0 3 0 1
Complexity Analysis For BFS Approach
Time Complexity: O(M*N)
- Here, M and N are the numbers of rows and columns, respectively.
- In the worst case, each pixel or element of the screen or array may be traversed hence, making the complexity to the order of (M*N).
Space Complexity: O(M*N)
- Here, M and N are the number of rows and columns in the image, respectively.
- In the worst case, O(M * N) extra space is required by the queue. Hence the overall space complexity is O(M * N).
If you are looking for a guide to mastering graph algorithms such as BFS and DFS.
Coding Ninjas has your back; check out this amazing blog and become an expert in Graphs.
Note: If you’ve ever used the bucket fill tool in MS paint or photo editing software like Photoshop or Gimp, you’re already familiar with the flood fill algorithm.
That’s shocking, isn’t it? Because you may not have realised it previously.
Indeed learning these algorithms is critical if you want to work in software companies as a technophile because you are constantly surrounded by them unknowingly.
If you also aspire to be in big product-based companies, check out Must Do Algorithms for Placements to ace your technical interview.
Frequently Asked Questions
The flood fill algorithm is basically used to change the colour of desired pixels to a new colour. It can be implemented using any of the above two methods that either use recursion or the concept of bfs.
As implemented above, yes, it is a recursive algorithm.
No, both are different as the flood fill algorithm is used to paint some selected interior of pixels by a different colour than the earlier one. And in the boundary fill algorithm, the interior is painted by continuously looking at the boundary colours.
You can implement the BFS approach of flood fill algorithm non-recursively by taking the help of an implicit stack.
Key Takeaways
So, the idea of solving this problem was simply changing the colour of the given pixel and then checking for all its four directions and similarly changing their colour too.
So, if the problem is clear, don’t leave it here only.
Jump on to solve the Flood-fill problem on Code Studio and get it accepted right away.
Having your toolkit ready with CodeStudio now, you are all set to carry forward your journey to join your dream company. While CodeStudio can provide you with everything you need, your diligence and hard work will carry you to success.
Are you feeling nervous? Don’t panic and go through some interview experiences and get ready to shine.
Be determined enough and have that passion in your hearts. You can do it.
Keep learning, keep growing!
Leave a Reply