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