Flood Fill LeetCode

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]

Recursive Method

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