Home » Technical Interview Questions » Algorithm Interview Questions » Flood Fill LeetCode

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.

Flood Fill LeetCode

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.

READ  K Empty Slots LeetCode

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

References

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions
Core Java Interview Questions

AD Blocker Detected !

Advertisements help running this website for free.

To view the content please disable AdBlocker and refresh the page.

Wait !!!

You can Crack Technical Interviews of Companies like Amazon, Google, LinkedIn, Facebook, PayPal, Flipkart, etc

Abhishek

Abhishek was able to crack Microsoft after practicing questions from TutorialCup