Last Updated: 8 Jan, 2021

Flood Fill

Moderate

Asked in companies

Solve now

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]

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

Solve now

Approaches

01 Approach

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:

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

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

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.
Replace the pixel value of the current coordinate ('currentX', ‘currentY’) with ‘P’.
Visit all neighbours of the current coordinate ('currentX', 'currentY') .

Solve now

02 Approach

The idea is here to run a BFS starting from a given coordinate ('X', ‘Y’) and visit all elements that are reachable from ('X', ‘Y’).

The steps are as follows:

Let us denote pixel value at a given coordinate by ‘C’.
Declare an empty queue of pairs and push {'X', ‘Y’} to it.
Run a loop until the queue is not empty, and do:
- Pop the front item from the queue and visit all its neighbours.
- If the pixel value of neighbour equals ‘C’ then change it to ‘P’.

4. At last, return the ‘IMAGE’.

Solve now