Home/

...

/

Flood Fill

Flood Fill

Try to solve the Flood Fill problem.

Statement

You are given a 2D grid of size m x n, where grid[i][j] represents the pixel value at position (i, j).

Additionally, you are given three integers:

  • sr: The row index of the starting pixel

  • sc: The column index of the starting pixel

  • target: The new color to apply

Your task is to perform a flood fill starting from the pixel at position (sr, sc). Below is the flood fill process:

  1. If the pixel at (sr, sc) already has the value target, return the original grid without any changes.

  2. Otherwise, start at the pixel grid[sr][sc] and change its color to the given color target.

  3. Perform the same operation for all 4-directionally adjacent pixels (up, down, left, right) with the same original color as the starting pixel.

  4. Continue this process by examining the neighboring pixels of each updated pixel and changing their color if they match the original color of the starting pixel.

  5. The process continues until no more adjacent pixels with the original color left to update.

Return the updated grid after the flood fill is complete.

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
5
6

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.