🦄 Pasture Paint: Flood Fill

Difficulty: Intermediate Tags: dfs, bfs, grid, graph-traversal, recursion Series: CS 102: Problem Solving & Logic

Problem

In the mystical pasture, magical paint spreads to all connected areas of the same color. Implement the classic flood fill algorithm used in paint programs.

Given a 2D grid representing an image where each cell has a color (integer), a starting cell (sr, sc), and a newColor, perform a flood fill. Change the color of the starting cell and all 4-directionally connected cells of the same original color to the new color.

Real-World Application

Flood fill appears in: - Paint programs - bucket fill tool in Photoshop, MS Paint - Image editing - background removal, color replacement - Game development - territory control, pathfinding, map generation - Computer vision - image segmentation, connected component analysis - Puzzle games - match-3 games, flood-it puzzles - GIS systems - region selection, area calculation - Medical imaging - organ segmentation, tumor detection

Input

data = {
    'image': List[List[int]],  # 2D grid of colors (integers)
    'sr': int,                  # Starting row
    'sc': int,                  # Starting column
    'newColor': int             # New color to fill
}

Output

List[List[int]]  # Modified image after flood fill

Constraints

• rows, cols ≤ 1,000
• Color values are integers
• 4-directional connectivity (up, down, left, right only)

Examples

Example 1: Basic Flood Fill

Input:

{
    'image': [[1,1,1],
              [1,1,0],
              [1,0,1]],
    'sr': 1,
    'sc': 1,
    'newColor': 2
}

Output:

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

Explanation: - Start at (1,1) which has color 1 - Fill all connected cells with color 1 → color 2 - Cells (0,0), (0,1), (0,2), (1,0), (1,1), (2,0) are connected and color 1 - They all become color 2

Example 2: Same Color (No-op)

Input:

{
    'image': [[0,0],
              [0,0]],
    'sr': 0,
    'sc': 0,
    'newColor': 0
}

Output:

[[0,0],
 [0,0]]

Explanation: - Old color equals new color - No change needed (important edge case!)

Example 3: Single Cell

Input:

{
    'image': [[5]],
    'sr': 0,
    'sc': 0,
    'newColor': 3
}

Output: [[3]]

What You'll Learn

• DFS (Depth-First Search) for grid traversal
• BFS (Breadth-First Search) alternative approach
• Handling the edge case when old color equals new color
• 4-directional grid navigation

Why This Matters

Flood fill demonstrates graph traversal fundamentals and appears frequently in: - Image processing interviews - Game development positions - Systems design discussions - Real-world tool implementation

Starter Code

def challenge_function(data):
    """
    Perform flood fill on image starting from (sr, sc).

    Args:
        data: dict with keys:
            - 'image' (List[List[int]]): 2D grid
            - 'sr' (int): starting row
            - 'sc' (int): starting column
            - 'newColor' (int): color to fill

    Returns:
        List[List[int]]: modified image
    """
    # Your implementation here
    pass