Flood Fill Algorithm

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-

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

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’. 
     
• 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 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!