Flood Fill

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
27 upvotes
Asked in companies
AdobeAmazonUber

Problem statement

An 'IMAGE' is represented by the 2-D array of positive integers, where each element of 2-D represents the pixel value of the image.


The given 'IMAGE' has 'N' rows and 'M' columns. You are given the location of the pixel in the image as ('X', 'Y')(0-based indexing) and a pixel value as 'P'.


Your task is to perform a “flood fill” operation on the given coordinate (X, Y) with pixel value 'P'.


Let the current pixel value of ('X', 'Y') be equal to C. To perform the flood fill operation on the coordinate (X, Y) with pixel value 'P' you need to do the following operations in order:

1. Replace the pixel value of ('X', 'Y') with 'P'.

2. Visit all non-diagonal neighbours of ('X', 'Y') having pixel values equal to C and replace their pixel value with 'P'.

3. Non – diagonal neighbours are Up('X' - 1, 'Y'), Down('X' + 1, 'Y'), Left('X', 'Y' - 1), right('X', 'Y' + 1). Also, you cannot go out of bounds.

4. Visit all non-diagonals neighbours of coordinates visited in step 2 having pixel value equal to C and replace their pixel value with 'P'. 

5. Repeat step 2, until you have visited all your neighbours
For Example: 
For  'N' = 5 , 'M' = 4 , 'X' = 2 , 'Y' = 2 and 'P' = 5
Given 'IMAGE' is shown below:

[7, 1, 1, 1]
[1, 7, 7, 7]
[7, 7, 7, 0]
[7, 7, 7, 4]
[4, 4, 4, 4]

After the flood fill operation, we will replace all neighbour's 7s with 5.

So our 'IMAGE' will become:

[7, 1, 1, 1]
[1, 5, 5, 5]
[5, 5, 5, 0]
[5, 5, 5, 4]
[4, 4, 4, 4]
Detailed explanation ( Input/output format, Notes, Images )
Input format: 
The first line contains two space-separated integers 'N' and 'M', denoting the number of rows and columns respectively.

The second line contains three space-separated integers, 'X', 'Y' and 'P', denoting starting coordinates of the pixel and the new pixel value of the flood fill operation.

The next 'N' lines will contain 'M' space-separated integers denoting elements of the image array.
Output format: 
Return a 2D matrix/array of size N * M representing the 'IMAGE' after performing the flood fill operation.
Note: 
You do not need to print anything, it has already been taken care of. Just implement the given function
Sample Input 1 :
3 2
1 1 3
0 0
1 1
1 0
Sample Output 1 :
0 0
3 3
3 0
Explanation :
We will replace all 1’s with 4 except the one which is at the bottom right corner i.e. 3,3.
Sample Input 2 :
4 3
1 1 4
0 0 2
1 1 2
1 0 2
2 2 1
Sample Output 2 :
0 0 2
4 4 2
4 0 2
2 2 1
Constraints :
1 <= N,M <= 100 
0 <= X <= N – 1
0 <= Y <= M - 1
0 <= IMAGE[i][j], P <= 10^9

Where 'IMAGE[i][j]' denotes the image matrix pixel elements.

Time limit: 1 sec
Hint

Think of a solution to using dfs.

Approaches (2)
Depth First Search

In this solution, we will run a dfs starting from a given coordinate ('X', ‘Y’) and visit all its adjacent elements and mark all of them by replacing their pixel value with ‘P’.

 

The steps are as follows:

 

  1. Initially declare ‘rowSize’ with ‘N’, and ‘columnSize’ with ‘M’.
  2. Check if ‘IMAGE[X][Y]’ = ‘P’ then return ‘IMAGE’.
  3. call dfs(‘IMAGE’, 'N', ‘M’, ‘X’, ‘Y’, ‘P’, ‘IMAGE[X}[Y]’) function.
  4. At last return ‘IMAGE’.

 

void dfs(‘IMAGE’, ‘N’, ‘M’, ‘currentX’, ‘currentY’, ‘P’, ‘C’):

  1. Check if current coordinate ('currentX', ‘currentY’) is out of bound or not and its pixel value equals to 'C" or not, If yes then stop dfs and return.
  2. Replace the pixel value of the current coordinate ('currentX', ‘currentY’) with ‘P’.
  3. Visit all neighbours of the current coordinate ('currentX', 'currentY') .
Time Complexity

O(N * M), Where ‘N’ is the total number of rows and ‘M’ is the total number of columns in the array.

 

Since we need to visit all the elements of the image. Hence the overall time complexity will be O(N * M). 

Space Complexity

O(N * M), Where ‘N’ is the total number of rows and ‘M’ is the total number of columns in the array.

 

Since we need O(N * M) recursion calls. This case happens when all elements of the matrix/image are the same and we need to visit all N * M cells, so our recursion stack will require O(N * M) space.  Hence the overall space complexity will be O(N * M).

Code Solution
(100% EXP penalty)
Flood Fill
Full screen
Console