How do you solve Flood Fill?

Use DFS starting at (sr, sc). For each pixel, if it is within bounds and matches the original color, recolor it and recursively visit its 4-directional neighbors. This approach guarantees all connected pixels are recolored exactly once, achieving O(m*n) time in the worst case.

What pattern does Flood Fill use?

The Pattern: DFS (Grid Connected Component Traversal) The Heuristic: When recoloring or marking connected regions in a grid, use DFS or BFS to traverse only the connected component starting from the source, ensuring efficient and correct updates without scanning unrelated areas.

Flood Fill — DFS

Q: What is the time complexity of Flood Fill?

O(m * n). Each pixel is visited at most once during the DFS traversal. The grid has m rows and n columns, so the worst-case time is proportional to the total number of pixels.

Problem

Given a 2D integer array image representing an image, a starting pixel (sr, sc), and a color, return the image after performing a flood fill on the starting pixel, changing the color of all connected pixels with the same original color to the new color.

m == image.length
n == image[i].length
1 ≤ m, n ≤ 50
0 ≤ image[i][j], color < 2¹⁶
0 ≤ sr < m
0 ≤ sc < n

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]]

We begin at pixel (1,1). Its original color is 1, so our goal is to recolor the entire region of 1s that is connected to (1,1) using only up, down, left, and right moves. First, we recolor (1,1) from 1 to 2. This is important for two reasons: it applies the requested change, and it also marks the pixel as already processed so we do not loop back to it later. Next, we check the four neighbors of (1,1): - Up at (0,1) has color 1, which matches the original color, so it belongs to the same reachable region and we recolor it to 2. - Down at (2,1) has color 0, which does not match the original color, so it is not part of the region we are filling and it must remain unchanged. - Left at (1,0) has color 1, which matches the original color, so it is part of the reachable region and we recolor it to 2. - Right at (1,2) has color 0, which does not match the original color, so it is not filled. From the newly recolored pixels, we repeat the same process: for every pixel we recolor to 2, we again inspect its up, down, left, and right neighbors. Whenever a neighbor is inside the grid and still has the original color 1, we recolor it to 2 as well. This continues until there are no more reachable neighbors with color 1. The pixel (2,2) stays as 1 even though it is a 1, because it cannot be reached from (1,1) by moving only up, down, left, and right through 1s. It is only diagonally adjacent, and diagonal adjacency does not count for flood fill in this problem.

Approach

Straightforward Solution

A naive approach would scan the entire grid and recolor every pixel whose value equals the starting color. This is inefficient because it touches many pixels that are unrelated to the starting area. More importantly, it is incorrect because it would also recolor pixels with the same value that are separated by barriers of other colors and are not reachable from (sr, sc) using only up, down, left, and right moves.

Core Observation

Flood fill is about recoloring a single “region” of pixels. The region is defined by two rules: you can only move up, down, left, or right, and you can only move through pixels that have the same original color as the start pixel. The algorithm’s job is to visit every reachable pixel that satisfies those rules and recolor it.

Path to Optimal

Preview

Recognizing the problem as a graph traversal on a grid, the optimal approach uses DFS or BFS starting from the source pixel. This traversal visits only the connected pixels with the original color, recoloring them in-place…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use DFS starting at (sr, sc). For each pixel, if it is within bounds and matches the original color, recolor it and recursively visit its 4-directional neighbors…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(m * n)

Each pixel is visited at most once during the DFS traversal. The grid has m rows and n columns, so the worst-case time is proportional to the total number of pixels.

Space

O(m * n)

In the worst case, the recursion stack can grow to the size of the entire grid if all pixels are connected and need recoloring. This is auxiliary space used by the DFS recursion.

Solution

Python

1class Solution:
  def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
      m, n = len(image), len(image[0])
      source = image[sr][sc]
      if source == color:
          return image
7
      directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
9
      def is_valid(r, c):
          return 0 <= r < m and 0 <= c < n
12
      def dfs(r, c):
          if not is_valid(r, c) or image[r][c] != source:
              return
          image[r][c] = color
          for dr, dc in directions:
              dfs(r + dr, c + dc)
19
      dfs(sr, sc)
      return image

Step-by-Step Solution

1

Capture Image Dimensions and Source Color for Reference

3m, n = len(image), len(image[0])
4source = image[sr][sc]

Objective

To store the dimensions of the image and the original color of the starting pixel for boundary and color checks during traversal.

Key Insight

Knowing the image size allows for efficient boundary checks to prevent invalid accesses. Capturing the source color upfront enables the algorithm to identify which pixels belong to the connected component that needs recoloring. This setup is essential for correctness and efficiency.

Interview Quick-Check

Core Logic

Storing image dimensions and source color upfront avoids repeated computations and clarifies the traversal conditions.

Common Pitfalls & Bugs

Forgetting to capture the source color before any recoloring can cause incorrect behavior if the starting pixel's color is the same as the new color.

2

Return Early if Source Color Equals Target Color

To avoid unnecessary work by returning the image immediately if the starting pixel's color is already the target color.

3

Define Valid Neighbor Directions for 4-Directional Traversal

To specify the relative coordinate offsets representing the four possible directions (up, down, left, right) for neighbor exploration.

4

Implement Boundary Check Helper to Validate Coordinates

To create a helper function that returns whether given coordinates are within the image boundaries.

5

Recursively Traverse and Recolor Connected Pixels Using DFS

To perform a depth-first search starting from the current pixel, recoloring it if it matches the source color, and recursively visiting all valid neighbors.

6

Initiate DFS from Starting Pixel and Return Modified Image

To start the DFS traversal from the given starting pixel and return the updated image after flood fill completion.

5 more steps with full analysis available on Pro.

Line Analysis

This solution has 4 Critical lines interviewers watch for.

Line 16 Critical

image[r][c] = color

Recolor the current pixel with the target color.

This line is the heart of the flood fill; recoloring the pixel both updates the image and acts as a visited marker, preventing infinite recursion and ensuring the connected component is correctly transformed.

Line 5 Critical

if source == color:

Check if the source color is the same as the target color.

If source == color, DFS would not make progress because pixels never change to mark them as visited, which can lead to runaway recursion. Returning early avoids that and avoids wasted work.

Line 14 Critical

if not is_valid(r, c) or image[r][c] != source:

Return if the current pixel is out of bounds or does not match the source color.

This base case prevents infinite recursion and ensures only pixels in the connected component are recolored.

Full line-by-line criticality + rationale for all 15 lines available on Pro.

Test Your Understanding

Why must the algorithm check if the current pixel's color matches the original source color before recoloring and recursing?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Flood Fill from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Flood Fill drill

or drill a free problem

1	`class Solution:`
2	`def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:`
3	`m, n = len(image), len(image[0])`
4	`source = image[sr][sc]`
5	`if source == color:`
6	`return image`
7
8	`directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]`
9
10	`def is_valid(r, c):`
11	`return 0 <= r < m and 0 <= c < n`
12
13	`def dfs(r, c):`
14	`if not is_valid(r, c) or image[r][c] != source:`
15	`return`
16	`image[r][c] = color`
17	`for dr, dc in directions:`
18	`dfs(r + dr, c + dc)`
19
20	`dfs(sr, sc)`
21	`return image`