Home/

...

/

Flood Fill

Flood Fill

Try to solve the Flood Fill problem.

Statement

We are given the following values as input to begin with:

  • The coordinates of a source cell, i.e., sr and sc.

  • A target value, target.

  • An (m×n)(m \times n) grid.

Our task is to perform flood fill by updating the values of the four directionally connected cells, which have the same value as the source cell with the target value.

How to perform flood fill:

Suppose that a (4×4)(4 \times 4) grid has a source value of 11 at coordinates [1,1][1, 1]. We perform flood fill on its neighboring cells only if they have the same source value as this cell. Once all adjacent cells are updated, return the new grid after performing flood fill.

If no neighboring cell has a value equal to the source cell, only update the source cell with the target value and return the updated grid.

Constraints:

  • 1≤1 \leq grid.length, grid[i].length ≤30\leq 30

  • 0≤0 \leq grid[i][j], target ≤216\leq 2^{16}

  • 0≤0 \leq sr <\lt grid.length

  • 0≤0 \leq sc <\lt grid[i].length

Examples

Understand the problem

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

Flood Fill

1

What is the correct output for the following input values?

grid=[1,1,0,1][0,1,1,1][1,0,0,1][1,1,1,1], sr=1, sc=3, target=3grid = \begin{matrix} [1, 1, 0, 1] \\ [0, 1, 1, 1] \\ [1, 0, 0, 1] \\ [1, 1, 1, 1] \end{matrix} ,\space sr = 1,\space sc = 3,\space target = 3

A)

[2,2,0,2][0,2,2,2][2,0,0,2][2,2,2,2] \begin{matrix} [2, 2, 0, 2] \\ [0, 2, 2, 2] \\ [2, 0, 0, 2] \\ [2, 2, 2, 2] \end{matrix}

B)

[3,3,0,3][0,3,3,3][3,0,0,3][3,3,3,3] \begin{matrix} [3, 3, 0, 3] \\ [0, 3, 3, 3] \\ [3, 0, 0, 3] \\ [3, 3, 3, 3] \end{matrix}

C)

[1,1,0,3][0,0,3,3][3,0,0,3][3,3,3,3] \begin{matrix} [1, 1, 0, 3] \\ [0, 0, 3, 3] \\ [3, 0, 0, 3] \\ [3, 3, 3, 3] \end{matrix}

Question 1 of 30 attempted

Figure it out!

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Sequence - Vertical
Drag and drop the cards to rearrange them in the correct sequence.
1
2
3
4

Try it yourself

Implement your solution in the following coding playground:

Press + to interact
JavaScript
usercode > main.js
function floodFill(grid, sr, sc, target){

    

    // Replace this placeholder return statement with your code

    return [[]]

}



export { floodFill };
Flood Fill

Access this course and 1200+ top-rated courses and projects.