**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.

**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.

**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

- Remember, diagonal positions are not adjacent.

Below, C++ code is given for your better understanding:

**Code for Brute Force**

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

Also check out - __Rod Cutting Problem__

**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’.

- Pop-out the first element from the queue.
- 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**

**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.

**If you also aspire to be in big ****product-based companies****, check out **__Must Do Algorithms for Placements__** ****to ace your technical interview.**

Read More - __Time Complexity of Sorting Algorithms__

**Frequently Asked Questions**

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

Jump on to solve the __Flood-fill problem__ on __Code Studio__ and get it accepted right away.

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 experience and get ready to shine.

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

**Keep learning, keep growing!**