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.

What is Flood Fill Algorithm?

Flood fill, also known as seed fill, is a flooding algorithm that chooses and modifies the region in a multidimensional array associated to a specific node with a particular attribute. It is used in games like Go and Minesweeper to determine which pieces are cleared as well as in paint applications' "bucket" fill tool to fill connected, similarly colored areas with a distinct color.

The area connected to a given node but lacking a specific characteristic is what is meant by the variation known as border fill, which uses the same techniques. It should be noted that flood filling is not appropriate for creating filled polygons because it will miss some pixels in more sharp corners.

Get the tech career you deserve, faster!

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

How does it work?

The solution is usually straightforward and consists of the following steps:

Consider the beginning point's location

Choose whether to travel in four directions (N, S, W, E) or eight directions (N, S, W, E, NW, NE, SW, SE)

Select a replacement and a target color

Go in those directions

If you land on a target tile, replace it with the desired color

Repeat steps 4 and 5 until you've visited every location inside the borders

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

C++

C++

#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).

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

C++

C++

#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 numbers 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).

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.

What is a flood fill algorithm and how does it work?

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.

Is the flood fill algorithm recursive?

As implemented above, yes, it is a recursive algorithm.

Is the flood fill algorithm the same as the boundary fill algorithm?

No, both are different as the flood fill algorithm is used to paint some selected interior of pixels with a different colour than the earlier one. And in the boundary fill algorithm, the interior is painted by continuously looking at the boundary colours.

What does it mean by a non-recursive flood fill algorithm?

You can implement the BFS approach of flood fill algorithm non-recursively by taking the help of an implicit stack.

Conclusion

The flood fill algorithm is a multi-dimensional array technique that determines a bounded area associated with a given node. It is similar to the bucket tool in paint programs.

So, if the problem is clear, don’t leave it here only.

Having your toolkit ready with Coding Ninjas Studio now, you are all set to carry forward your journey to join your dream company. While Coding Ninjas Studio 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 experienceand get ready to shine.

Be determined enough and have that passion in your hearts. You can do it.