#0056

Flood Fill a Grid

MediumDSA25 min20 XP

Problem

Given a grid of integers, a start row, a start column, and a new color, return the grid after recoloring the connected region that has the same original color as the start cell. Connectivity is up, down, left, and right.

Why This Matters

Grid DFS/BFS is the bridge from simple loops to graph traversal. It appears in image editing, maps, islands, maze search, and matrix problems.

Function Signature

def flood_fill(grid, sr, sc, new_color):

Examples

Example 1

Inputgrid = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, new_color = 2

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

Only the connected 1-region touching the start cell is recolored.

Constraints

The grid has at least one row and one column.
Modify and return the grid.
Use four-directional connectivity.

CodePython

def flood_fill(grid, sr, sc, new_color):
    """
    Input example: grid = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, new_color = 2
    Return: [[2,2,2],[2,2,0],[2,0,1]]
    Return the value from the function so the tests can compare it. Do not print unless the prompt asks.
    """
    # write your code here
    return grid

def flood_fill(grid, sr, sc, new_color):
    """
    Input example: grid = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, new_color = 2
    Return: [[2,2,2],[2,2,0],[2,0,1]]
    Return the value from the function so the tests can compare it. Do not print unless the prompt asks.
    """
    # write your code here
    return grid

Visible browser tests run here when available.

Testcases1 visible / 3 hidden categories

Connected region only

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

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

The bottom-right 1 is diagonal only, so it stays unchanged.

Hidden Test Categories

New color equals original colorSingle-cell gridRegion touches edges