# Flood Fill LeetCode

Difficulty Level Easy
algorithms coding Depth First Search Interview interviewprep LeetCode LeetCodeSolutions MatrixViews 1855

In Flood Fill problem we have given a 2D array a[ ][ ] representing an image of size mxn with each value representing the color of the pixel at that co-ordinate. Also given the location or coordinates of a pixel and a color. Replace the color at a given location and all adjacent coordinates or locations with the same color as a given location with the given color. Print the array representing new colors in the image. ## Example

Now have a look for examples of flood fill algorithm.

Input :

a[ ][ ] = [ [ 1 1 1 ]

[ 1 1 0 ]

[1 0 1 ] ]

x = 1

y = 1

color = 2

Output :

[ 2 2 2 ]

[ 2 2 0 ]

[ 2 0 1 ]

Input :

a[ ][ ] = [ [ 1 1 0 ]

[ 1 1 0 ]

[ 1 0 0 ] ]

x = 1

y = 3

color = 5

Output :

[1 1 5]

[1 1 5]

[1 5 5]

## Algorithm for Flood Fill LeetCode

1. Initialize a 2D array a[ ][ ] of size mxn where m is equal to n representing an image in pixels form with each pixel representing it’s color.
2. Also initialize two co-ordinates x, y, and a color.
3. If x and y are less than 0 or greater than m or n, return.
4. Store the color at coordinates x and y in a variable prevC.
5. Check if color at coordinates x and y is not equal to prevC i.e. previous color, return.
6. If color at coordinates x and y is equal to a new color, return.
7. Else update the color at coordinates x and y as a new color.
8. Make four recursive calls to the function with co-ordinates as (x+1, y), (x-1, y), (x, y+1) and (x, y-1).
9. Print the updated 2D array.

## C++ Program for Flood Fill LeetCode

```#include<iostream>
using namespace std;

#define m 3
#define n 3

void floodFill(int a[][n], int x, int y, int prevC, int newC){

if(x<0 || x>=m || y<0 || y>=n)
return;
if(a[x][y] != prevC)
return;
if(a[x][y] == newC)
return;

a[x][y] = newC;

floodFill(a, x+1, y, prevC, newC);
floodFill(a, x-1, y, prevC, newC);
floodFill(a, x, y+1, prevC, newC);
floodFill(a, x, y-1, prevC, newC);
}

void Fill(int a[][n], int x, int y, int color){
int prevColor = a[x][y];
floodFill(a, x, y, prevColor, color);
}

int main(){

int a[m][n] = {{1, 1, 1},
{1, 1, 0},
{1, 0, 1},
};
int x = 1, y = 1, color = 2;

Fill(a, x, y, color);

for(int i=0; i<m; i++){

cout<<"[ ";
for (int j=0; j<m; j++)
cout<<a[i][j]<<" ";
cout<<"]\n";
}
}```
```[ 2 2 2 ]
[ 2 2 0 ]
[ 2 0 1 ]```

## Java Program for Flood Fill LeetCode

```class floodfill{

static int m = 3;
static int n = 3;

static void floodFill(int a[][], int x, int y, int prevC, int newC){

if(x<0 || x>=m || y<0 || y>=n)
return;
if(a[x][y] != prevC)
return;

a[x][y] = newC;

floodFill(a, x+1, y, prevC, newC);
floodFill(a, x-1, y, prevC, newC);
floodFill(a, x, y+1, prevC, newC);
floodFill(a, x, y-1, prevC, newC);
}

static void Fill(int a[][], int x, int y, int color){
int prevColor = a[x][y];
floodFill(a, x, y, prevColor, color);
}

public static void main(String[] args){
int a[][] = {{1, 1, 1},
{1, 1, 0},
{1, 0, 1},
};
int x = 1, y = 1, color = 2;
Fill(a, x, y, color);

for(int i=0; i<m; i++){
System.out.print("[ ");
for(int j=0; j<n; j++)
System.out.print(a[i][j]+" ");
System.out.print("]");
System.out.println();
}
}
}```
```[ 2 2 2 ]
[ 2 2 0 ]
[ 2 0 1 ]```

## Complexity Analysis for Flood Fill LeetCode

Time Complexity: O(N) where N is the number of elements which is equal to Row*Column. i.e. number image pixels.

Auxiliary Space: O(1) because we don’t use any auxiliary space in implementation.

References

Translate »