Solution: Flood Fill

Let's solve the Flood Fill problem using the Backtracking pattern.

We'll cover the following

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

Solution

The solution uses depth-first search to recursively explore and update all connected pixels that share the same original color as the starting pixel at (sr, sc). DFS starts by recording the original color and checking if it already matches the target color, in which case, the grid is returned unchanged. Otherwise, the starting pixel’s color is updated to the target color, and DFS is applied to each of its four 4-directionally adjacent neighbors (up, down, left, right). For each neighbor, the algorithm checks two conditions: the cell must be within the grid boundaries (i.e., row and column indexes are valid: 0 ≤ row < m and 0 ≤ col < n), and the cell’s color must match the original color. Only when both conditions are met does DFS proceed to that cell. The recursion naturally terminates when no more valid neighboring pixels satisfy these conditions, ensuring that only the correct, connected region is filled.

If a cell is out of bounds or its value doesn’t match the original color, the recursion stops in that direction. No need to undo changes—DFS only proceeds when valid, so backtracking is handled naturally.

The steps of the algorithm are as follows:

  1. If the starting cell (sr, sc) already has the target value, return immediately—no changes are needed.

  2. Save the value of the starting cell as old_target. We’ll only modify cells with this value.

  3. Color the starting cell by assigning grid[sr][sc] = target to begin the fill.

  4. Recursive DFS: For each of the four adjacent cells (up, down, left, right), do the following:

    1. Check if the cell is within bounds: i < grid_length and i >= 0 and j < total_cells and j >= 0.

    2. Check if its value matches old_target.

    3. If both conditions are true:

      1. Change its value to the target.

      2. Recursively apply DFS to this cell.

  5. The recursion ends once all connected, same-colored cells are filled. We then return the modified grid.

The following illustration shows these steps in detail:

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.