Problem Description

You have an m x n grid representing an image where each cell image[i][j] contains an integer representing a pixel's color value. You need to perform a flood fill operation starting from a specific pixel at position (sr, sc) and change it to a new color value.

The flood fill operation works like the paint bucket tool in image editing software:

1. Start at the pixel image[sr][sc] and change its color to the given color
2. Find all pixels that are directly connected to this pixel (up, down, left, right - not diagonally) that have the same original color as the starting pixel
3. Change all these connected pixels to the new color
4. Continue this process recursively for each newly colored pixel, finding and coloring their neighbors that match the original color
5. Stop when no more pixels with the original color can be reached

The goal is to change the color of all pixels that:

• Are connected to the starting pixel through a path of adjacent pixels (horizontally or vertically)
• Share the same color as the original color of the starting pixel

Return the modified image after completing the flood fill operation.

For example, if you start at a pixel with color value 1, all connected pixels with color value 1 should be changed to the new color, but pixels with different colors or pixels not connected to the starting pixel remain unchanged.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: The image grid can be viewed as a graph where each pixel is a node, and edges connect adjacent pixels (horizontally and vertically). We need to traverse connected components of pixels with the same color.

Is it a tree?

• No: The grid structure is not a tree. It's a 2D grid where pixels can form cycles (e.g., four pixels forming a square all with the same color would create a cycle).

Is the problem related to directed acyclic graphs?

• No: The problem doesn't involve directed edges or acyclic properties. The flood fill explores bidirectionally between adjacent pixels.

Is the problem related to shortest paths?

• No: We're not finding shortest paths between pixels. Instead, we need to visit all connected pixels with the same color.

Does the problem involve connectivity?

• Yes: The core of flood fill is finding all pixels connected to the starting pixel that share the same original color. This is essentially finding a connected component in the graph.

Does the problem have small constraints?

• Yes: Image grids typically have reasonable dimensions (m × n), making recursive approaches feasible without stack overflow concerns.

DFS/backtracking?

• Yes: DFS is perfect for exploring all connected pixels recursively. Starting from the initial pixel, we recursively visit all adjacent pixels with the same color and change them.

Conclusion: The flowchart leads us to use DFS (Depth-First Search) for the flood fill algorithm. DFS naturally explores connected components by recursively visiting neighbors, which is exactly what flood fill requires - changing all connected pixels of the same color.

Intuition

Think of the flood fill operation like spilling paint on a connected surface - the paint naturally flows to all connected areas of the same material. In our case, the "same material" means pixels with the same color value.

The key insight is recognizing that we need to explore all pixels that are:

1. Reachable from our starting point through adjacent moves (up, down, left, right)
2. Have the same color as our starting pixel's original color

This is a classic connected component problem. When we change a pixel's color, we need to check its four neighbors. If any neighbor has the original color, we should change it too and then check its neighbors. This recursive nature of "change current pixel, then check and process neighbors" naturally leads us to DFS.

Why DFS over BFS? Both would work, but DFS is more intuitive here because:

• We can implement it recursively with cleaner code
• We don't need to track the level or distance (which BFS excels at)
• We just need to visit all connected pixels, and DFS does this efficiently by going as deep as possible before backtracking

The critical edge case to handle is when the new color equals the original color. If we don't check for this, we'd get stuck in infinite recursion - we'd keep "recoloring" the same pixels with the same color forever. That's why the solution checks if oc != color before starting the DFS.

The algorithm naturally terminates when we've visited all pixels in the connected component because:

• Changed pixels now have a different color than the original
• Our DFS only continues for pixels matching the original color
• This creates a natural boundary that stops the recursion

Learn more about Depth-First Search and Breadth-First Search patterns.

Solution Approach

The solution implements a DFS approach to perform the flood fill operation. Let's break down the implementation step by step:

Initial Setup:

• Store the original color of the starting pixel: oc = image[sr][sc]
• Check if the original color is different from the target color: if oc != color
• If they're the same, no work needs to be done - return the image as is

DFS Function: The core of the solution is the recursive dfs(i, j) function that:

1. Changes the current pixel's color: image[i][j] = color
2. Explores all four adjacent directions (up, down, left, right)

Direction Traversal: The solution uses a clever pattern with dirs = (-1, 0, 1, 0, -1) and pairwise:

• pairwise(dirs) generates pairs: (-1, 0), (0, 1), (1, 0), (0, -1)
• These pairs represent direction vectors: up, right, down, left
• For each direction (a, b), calculate the new position: x, y = i + a, j + b

Boundary and Color Checking: Before recursing to a neighbor pixel, three conditions must be met:

1. 0 <= x < len(image): The row index is within bounds
2. 0 <= y < len(image[0]): The column index is within bounds
3. image[x][y] == oc: The neighbor pixel has the original color

If all conditions are satisfied, recursively call dfs(x, y) to process that neighbor.

Why This Works:

• The recursion naturally handles the "spreading" effect of flood fill
• By checking image[x][y] == oc before recursing, we ensure we only process pixels with the original color
• Once a pixel is changed to the new color, it won't be processed again (preventing infinite recursion)
• The DFS explores as far as possible in each direction before backtracking, efficiently covering all connected pixels

Time Complexity: O(m × n) where m and n are the dimensions of the image, as we might need to visit every pixel once in the worst case.

Space Complexity: O(m × n) for the recursion stack in the worst case when all pixels need to be filled.

Example Walkthrough

Let's walk through a small example to illustrate the flood fill algorithm:

Initial Setup:

image = [[1, 1, 1],
         [1, 1, 0],
         [1, 0, 1]]

Starting position: (sr, sc) = (1, 1)
New color: 2

Step 1: Initialize

• Original color at position (1,1): oc = image[1][1] = 1
• Since oc (1) ≠ color (2), we proceed with the DFS

Step 2: Start DFS at (1,1)

• Change image[1][1] = 2
• Image becomes:

[[1, 1, 1],
 [1, 2, 0],
 [1, 0, 1]]

• Check 4 neighbors:
  • Up (0,1): Has value 1 (matches original) ✓
  • Right (1,2): Has value 0 (doesn't match) ✗
  • Down (2,1): Has value 0 (doesn't match) ✗
  • Left (1,0): Has value 1 (matches original) ✓

Step 3: DFS to (0,1)

• Change image[0][1] = 2
• Image becomes:

[[1, 2, 1],
 [1, 2, 0],
 [1, 0, 1]]

• Check neighbors:
  • Up: Out of bounds ✗
  • Right (0,2): Has value 1 ✓
  • Down (1,1): Has value 2 (already changed) ✗
  • Left (0,0): Has value 1 ✓

Step 4: DFS to (0,2)

• Change image[0][2] = 2
• Image becomes:

[[1, 2, 2],
 [1, 2, 0],
 [1, 0, 1]]

• Check neighbors: None have original color 1 that are reachable

Step 5: Backtrack and DFS to (0,0)

• Change image[0][0] = 2
• Image becomes:

[[2, 2, 2],
 [1, 2, 0],
 [1, 0, 1]]

• Check neighbors:
  • Right (0,1): Already value 2 ✗
  • Down (1,0): Has value 1 ✓

Step 6: DFS to (1,0)

• Change image[1][0] = 2
• Image becomes:

[[2, 2, 2],
 [2, 2, 0],
 [1, 0, 1]]

• Check neighbors:
  • Up (0,0): Already value 2 ✗
  • Right (1,1): Already value 2 ✗
  • Down (2,0): Has value 1 ✓

Step 7: DFS to (2,0)

• Change image[2][0] = 2
• Final image:

[[2, 2, 2],
 [2, 2, 0],
 [2, 0, 1]]

• No more neighbors with original color 1

Result: All pixels with value 1 that were connected to position (1,1) have been changed to 2. The pixels with value 0 act as barriers, and the pixel at (2,2) with value 1 remains unchanged because it's not connected to our starting point through pixels of the same color.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m × n) where m is the number of rows and n is the number of columns in the image.

In the worst case, the flood fill algorithm needs to visit every pixel in the image. This happens when all pixels have the same color as the starting pixel and need to be changed. The DFS traversal visits each pixel at most once (since we change the color when visiting, preventing revisits), resulting in O(m × n) time complexity.

Space Complexity: O(m × n) where m is the number of rows and n is the number of columns in the image.

The space complexity is dominated by the recursive call stack in the DFS traversal. In the worst case, when all pixels need to be filled and form a long chain (like a spiral pattern), the recursion depth could reach O(m × n). This happens because each recursive call adds a frame to the call stack, and we might need to go through all pixels before backtracking begins.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Infinite Recursion When Original Color Equals New Color

The Problem: One of the most common mistakes is forgetting to check if the original color is the same as the new color before starting the flood fill. Without this check, the algorithm will infinitely recurse because:

• The pixel at (sr, sc) gets changed to color
• The DFS checks neighbors and finds they have the "original color"
• But since original color = new color, already-processed pixels still match the condition
• The algorithm revisits the same pixels repeatedly, causing stack overflow

Incorrect Implementation:

def floodFill(self, image, sr, sc, color):
    original_color = image[sr][sc]
    # Missing the check: if original_color == color: return image
  
    def dfs(row, col):
        image[row][col] = color
        for dr, dc in [(-1,0), (0,1), (1,0), (0,-1)]:
            new_row, new_col = row + dr, col + dc
            if (0 <= new_row < len(image) and 
                0 <= new_col < len(image[0]) and 
                image[new_row][new_col] == original_color):
                dfs(new_row, new_col)  # Infinite recursion!
  
    dfs(sr, sc)
    return image

The Solution: Always check if the original color differs from the target color before starting:

original_color = image[sr][sc]
if original_color == color:
    return image  # No work needed, prevents infinite recursion

Pitfall 2: Using a Visited Set Unnecessarily

The Problem: Some developers instinctively add a visited set to track processed pixels, similar to other graph traversal problems. While this works, it's unnecessary overhead for flood fill because:

• Once we change a pixel's color, it no longer matches the original color
• The color change itself acts as the "visited" marker
• Adding a visited set increases space complexity without benefit

Overcomplicated Implementation:

def floodFill(self, image, sr, sc, color):
    original_color = image[sr][sc]
    if original_color == color:
        return image
  
    visited = set()  # Unnecessary!
  
    def dfs(row, col):
        if (row, col) in visited:  # Extra check not needed
            return
        visited.add((row, col))
        image[row][col] = color
      
        for dr, dc in [(-1,0), (0,1), (1,0), (0,-1)]:
            new_row, new_col = row + dr, col + dc
            if (0 <= new_row < len(image) and 
                0 <= new_col < len(image[0]) and 
                image[new_row][new_col] == original_color):
                dfs(new_row, new_col)
  
    dfs(sr, sc)
    return image

The Solution: Trust that the color change prevents revisiting. The condition image[new_row][new_col] == original_color naturally excludes already-processed pixels since they now have the new color.

Pitfall 3: Modifying the Condition Check Order

The Problem: Checking the color condition before boundary checks can cause index out of bounds errors:

Incorrect Order:

# Wrong: color check before boundary check
if (image[new_row][new_col] == original_color and  # IndexError possible!
    0 <= new_row < rows and 
    0 <= new_col < cols):
    dfs(new_row, new_col)

The Solution: Always validate boundaries before accessing array elements:

# Correct: boundary check first
if (0 <= new_row < rows and 
    0 <= new_col < cols and 
    image[new_row][new_col] == original_color):
    dfs(new_row, new_col)

Python's short-circuit evaluation ensures the array access only happens after confirming valid indices.