easy

Flood Fill

Change the color of a connected region in an image, starting from one pixel.

1. Define the problem

Flood Fill

You are given an image represented by an m x n grid of integers, a starting pixel (sr, sc), and a new color. Perform a flood fill: starting from the given pixel, recolor every pixel that is connected to it (up, down, left, right) and shares the same original color. Return the modified image. Use depth-first search from the starting pixel, recoloring as you go and only stepping into a neighbor if it still has the original color — that doubles as your visited check.

Constraints

  • m == image.length
  • n == imagei.length
  • 1 ≤ m, n ≤ 50
  • 0 ≤ imagei[j], color < 216
  • 0 ≤ sr < m
  • 0 ≤ sc < n

Example

Inputimage = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2
Output[[2,2,2],[2,2,0],[2,0,1]]

Explanation Starting at (1,1), the connected region of 1s reachable from there — (1,1), (0,1), (0,0), (0,2), (1,0), (2,0) — is recolored to 2. The isolated 1 at (2,2) is not connected, so it stays 1.

2. Know the words first

In plain terms

Connected
Reachable by moving up, down, left, or right one cell at a time, through cells of the same starting color.
3. Visualize the solution

Recolor the connected region, one neighbor at a time

Recolor the connected region, one neighbor at a time
Statusstart

Start at (1,1), value 1. Recolor it to 2, then check its neighbors.

What happens in this step

dfs(index 4)  →  image[4] = 1

Recolor index 4 to 2.
  down  → index 7 = 0  (not the original color, skip)
  up    → index 1 = 1  (matches, step in next)
  right → index 5 = 0  (skip)
  left  → index 3 = 1  (matches, tried after up returns)

Recoloring happens immediately on arrival, before any neighbor is checked — that's what keeps this cell from being revisited later.
Step 1 of 5

Steps to visualize

  1. Start at (sr, sc) and recolor it immediately.
  2. Step into any 4-directional neighbor that still has the original color.
  3. Recolor that neighbor, then recurse from it the same way.
  4. A neighbor with a different color — or already recolored — is skipped.
  5. The fill stops naturally once every connected pixel of the original color has been recolored.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Recolor the connected region, one neighbor at a time
Statusstart

Start at (1,1), value 1. Recolor it to 2, then check its neighbors.

What happens in this step

dfs(index 4)  →  image[4] = 1

Recolor index 4 to 2.
  down  → index 7 = 0  (not the original color, skip)
  up    → index 1 = 1  (matches, step in next)
  right → index 5 = 0  (skip)
  left  → index 3 = 1  (matches, tried after up returns)

Recoloring happens immediately on arrival, before any neighbor is checked — that's what keeps this cell from being revisited later.
Step 1 of 5
5. Solution

Solution

solution.tsTypeScript
function floodFill(image, sr, sc, color) {
  const startColor = image[sr][sc];
  if (startColor === color) {
    return image;
  }

  const rows = image.length;
  const cols = image[0].length;

  function dfs(r, c) {
    if (r < 0 || r >= rows || c < 0 || c >= cols) return;
    if (image[r][c] !== startColor) return;

    image[r][c] = color;
    dfs(r + 1, c);
    dfs(r - 1, c);
    dfs(r, c + 1);
    dfs(r, c - 1);
  }

  dfs(sr, sc);
  return image;
}
Time
O(rows × cols)
Space
O(rows × cols)
6. Test cases

Test cases

InputExpectedCovers
image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2[[2,2,2],[2,2,0],[2,0,1]]example from the docstring
image = [[0,0,0],[0,1,1]], sr = 1, sc = 1, color = 1[[0,0,0],[0,1,1]]new color matches the starting color, nothing changes
image = [[0]], sr = 0, sc = 0, color = 1[[1]]smallest valid input, a single pixel
image = [[1,1],[1,1]], sr = 0, sc = 0, color = 2[[2,2],[2,2]]entire grid is one connected color
image = [[1,0],[0,1]], sr = 0, sc = 0, color = 2[[2,0],[0,1]]diagonal neighbors do not count as connected
image = [[1,1,2],[1,1,2],[2,2,2]], sr = 0, sc = 0, color = 3[[3,3,2],[3,3,2],[2,2,2]]a different color region blocks the fill from spreading further
image = [[0,0,0],[0,0,0],[0,0,0]], sr = 2, sc = 2, color = 5[[5,5,5],[5,5,5],[5,5,5]]starting pixel is not at the origin of the grid
image = [[1,1],[2,2]], sr = 0, sc = 0, color = 2[[2,2],[2,2]]the new color already appears in a disconnected region and is left untouched by it

Keep reading