Flood Fill

Difficulty: Easy

Problem

You are given an image as a 2D grid of integers, where each integer is a pixel color. You are also given a start pixel (sr, sc) and a new color. Repaint the start pixel AND every pixel connected to it 4-directionally (up, down, left, right) that shares its ORIGINAL color, and keep spreading through those pixels the same way. This is exactly the paint-bucket tool from every image editor. Return the repainted image.

Example

Input: image = [[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: All six 1s connected to the center 4-directionally get repainted to 2. The 1 in the bottom-right corner keeps its color: it only touches the region diagonally, and diagonals don't count.

Brute-force approach

There is no meaningful brute force vs optimal split. Flood fill IS the DFS you built in Graph Foundations, applied directly to the grid. Graph problems skip straight to the optimal approach.

Optimal approach

Key insight: The region to repaint is exactly the connected component of the old color containing (sr, sc). Paint each cell BEFORE spreading: a repainted cell no longer matches the old color, so the image itself becomes the visited set. One guard (old == color) removes the only infinite loop.

Save the start cell's color, then DFS outward from (sr, sc): paint every in-bounds cell that still shows the old color, and let each painted cell spread to its four neighbors. The paint itself marks cells visited.

Steps

  1. Save old = image[sr][sc]: the color that defines the region
  2. Guard: if old == color, return the image untouched, painting would change nothing, and without this the flood never terminates
  3. fill(r, c) stops at out-of-bounds cells and at cells that don't show old (that's the region boundary AND the visited check)
  4. Paint image[r][c] = color FIRST, the in-place visited mark
  5. Spread with fill(r-1, c), fill(r+1, c), fill(r, c-1), fill(r, c+1); kick off with fill(sr, sc) and return the image

Time complexity: O(rows × cols) · Space complexity: O(rows × cols) worst-case recursion depth