Flood fill a grid
Recolor the connected region containing a starting cell. Cells connect vertically and horizontally when they have the same original color.
Course progress
Problem 47 of 100
Example → approach → runnable solution
Worked example
See the problem in action
Trace a concrete input through to the verified result.
Example input
image = [[1,1,1],[1,1,0],[1,0,1]]; start = (1,1); replacement = 2
Expected output
2 2 2 2 2 0 2 0 1
What is happening?
The start belongs to the connected region of 1 values at the top-left. Those five connected cells become 2; disconnected cells remain unchanged.
Solution strategy
Build the right mental model
Remember the original color, recolor the current cell, and recursively visit valid neighbors that still have the original color.
Core concepts
grid · depth-first search
Complexity
Time O(rows x columns), call-stack space O(rows x columns) in the worst case.
Runnable solution
Learn from working code
Compare languages, copy the code, or open it in the compiler.
Complete C# solution for flood-fill
using System;
class Program
{
static void Fill(int[,] image, int row, int column, int original, int replacement)
{
if (row < 0 || row >= image.GetLength(0) ||
column < 0 || column >= image.GetLength(1) ||
image[row, column] != original) return;
image[row, column] = replacement;
Fill(image, row - 1, column, original, replacement);
Fill(image, row + 1, column, original, replacement);
Fill(image, row, column - 1, original, replacement);
Fill(image, row, column + 1, original, replacement);
}
static void FloodFill(int[,] image, int row, int column, int replacement)
{
int original = image[row, column];
if (original != replacement) Fill(image, row, column, original, replacement);
}
static void Main()
{
int[,] image = { { 1, 1, 1 }, { 1, 1, 0 }, { 1, 0, 1 } };
FloodFill(image, 1, 1, 2);
for (int row = 0; row < image.GetLength(0); row++)
{
for (int column = 0; column < image.GetLength(1); column++)
Console.Write((column == 0 ? "" : " ") + image[row, column]);
Console.WriteLine();
}
}
}Knowledge check
Questions students often ask
What is the main idea behind flood fill a grid?
Remember the original color, recolor the current cell, and recursively visit valid neighbors that still have the original color.
What is the time and space complexity of this solution?
Time O(rows x columns), call-stack space O(rows x columns) in the worst case.
Do all language tabs solve the same problem?
Yes. Every program uses the same example and produces the verified output shown on this page. The syntax and a few language-specific data structures differ.