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 - LeetCode Solution & Explanation

Q: 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.

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

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. This avoids unnecessary work and ensures correctness.

Optimal Approach

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.

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

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

5if source == color:
6    return image

Objective

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

Key Insight

If the source color matches the new color, no changes are needed. Without this check, the DFS would recurse infinitely or unnecessarily recolor pixels, causing inefficiency or stack overflow. This early exit is a critical optimization and correctness safeguard.

Interview Quick-Check

Core Logic

Early return prevents infinite recursion and redundant work when the source and target colors are identical.

3

Define Valid Neighbor Directions for 4-Directional Traversal

8	`directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]`

Objective

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

Key Insight

Explicitly defining directions as coordinate offsets simplifies neighbor traversal logic and makes the DFS code cleaner and less error-prone. This abstraction allows uniform iteration over neighbors without duplicating code.

Interview Quick-Check

Core Logic

Using a directions list abstracts neighbor exploration, enabling concise and maintainable recursive calls.

Common Pitfalls & Bugs

Forgetting to include all four directions or including invalid directions can cause incomplete or incorrect traversal.

4

Implement Boundary Check Helper to Validate Coordinates

10def is_valid(r, c):
11    return 0 <= r < m and 0 <= c < n

Objective

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

Key Insight

Separating boundary checks into a helper function improves code readability and reduces duplication. It centralizes the logic for coordinate validation, making the DFS function cleaner and easier to maintain.

Interview Quick-Check

Core Logic

A dedicated boundary check function ensures all neighbor coordinates are validated consistently before processing.

Common Pitfalls & Bugs

Neglecting boundary checks leads to index errors or invalid memory access.

5

Recursively Traverse and Recolor Connected Pixels Using DFS

13def 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)

Objective

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.

Key Insight

DFS explores the entire connected component by visiting each pixel exactly once. Recoloring upon visiting prevents revisiting the same pixel, effectively marking it as visited. Recursing over all four directions ensures complete coverage of the connected region. This approach guarantees correctness and efficiency by avoiding redundant work.

Interview Quick-Check

Core Logic

DFS recolors the current pixel and recursively explores all valid neighbors with the original color, ensuring full connected component traversal.

State & Boundaries

The base case returns when the pixel is out of bounds or does not match the source color, preventing infinite recursion.

Common Pitfalls & Bugs

Failing to recolor before recursion or not checking the pixel color can cause infinite loops or incorrect recoloring.

6

Initiate DFS from Starting Pixel and Return Modified Image

20dfs(sr, sc)
21return image

Objective

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

Key Insight

Calling DFS from the source pixel triggers the recursive recoloring of the entire connected component. Returning the image after traversal provides the final modified state as required by the problem.

Interview Quick-Check

Core Logic

Starting DFS at (sr, sc) ensures the entire connected component is recolored.

State & Boundaries

Returning the image after DFS completes provides the final flood-filled image.

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.

Line 18 Critical

dfs(r + dr, c + dc)

Recursively call DFS on the neighboring pixel.

Recursive calls propagate the flood fill to all connected pixels, enabling depth-first traversal of the component.

Line 4 Core

source = image[sr][sc]

Capture the original color of the starting pixel.

Storing the source color upfront is essential to identify which pixels belong to the connected component that needs recoloring, ensuring correctness.

Line 6 Core

return image

Return the original image immediately if no recoloring is needed.

Early return avoids redundant traversal and recoloring, ensuring efficiency and preventing stack overflow.

Line 20 Core

dfs(sr, sc)

Start DFS traversal from the starting pixel.

Initiating DFS here triggers the entire flood fill process, ensuring all connected pixels are recolored.

Line 10 Core

def is_valid(r, c):

Define a helper function to check if coordinates are within image bounds.

Centralizing boundary checks prevents index errors and makes the DFS code cleaner and more maintainable.

Line 11 Core

return 0 <= r < m and 0 <= c < n

Return whether the given coordinates are valid within the image.

This boolean check is the gatekeeper for safe access to image pixels during traversal.

Line 15 Core

return

Terminate the current DFS call without further recursion.

Returning here stops traversal along invalid or irrelevant paths, maintaining correctness and efficiency.

Line 8 Standard

directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

Define the four possible directions for neighbor traversal.

Explicitly listing directions simplifies neighbor exploration logic and ensures consistent 4-directional traversal.

Line 13 Standard

def dfs(r, c):

Define the DFS function to recolor connected pixels.

Encapsulating the recursive traversal logic in a helper function organizes the code and manages recursion state effectively.

Line 17 Standard

for dr, dc in directions:

Iterate over all four neighbor directions.

Looping over directions enables systematic exploration of all adjacent pixels, ensuring complete traversal of the connected component.

Line 3 Standard

m, n = len(image), len(image[0])

Store the number of rows and columns in the image.

Caching the image dimensions enables efficient boundary checks during traversal and avoids repeated calls to len(), improving readability and performance.

Line 21 Standard

return image

Return the modified image after flood fill completion.

Returning the updated image provides the final result as required by the problem statement.

Test Your Understanding

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

Because only pixels connected 4-directionally with the same original color should be recolored. Checking prevents recoloring pixels of different colors and avoids infinite recursion by not revisiting already recolored pixels.

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`

Problem

Example

Approach

Solution

Step-by-Step Solution

Capture Image Dimensions and Source Color for Reference

Return Early if Source Color Equals Target Color

Define Valid Neighbor Directions for 4-Directional Traversal

Implement Boundary Check Helper to Validate Coordinates

Recursively Traverse and Recolor Connected Pixels Using DFS

Initiate DFS from Starting Pixel and Return Modified Image

Line Analysis

Test Your Understanding

Related Problems

Don't just read it. Drill it.