Introduction

Flood Fill is one of the most popular Matrix DFS and BFS interview problems.

You are given:

image[][]sr
sc
color

Goal:

Change the color of all connected cells having the same original color.

Movement:

Up
Down
Left
Right

Example

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]]

Key Observation

Starting from:

(sr, sc)

Visit every connected cell having:

Original Color

Replace it with:

 New Color

Algorithm

1. Store original color.
2. Start DFS/BFS.
3. Visit valid neighbors.
4. Replace color.
5. Continue traversal.

Dry Run

Input:

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

Start:

(1,1)

Replace:

All connected 1s with 2

Answer:

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

Approach : DFS

Explanation

For every cell:

  1. Check boundaries.
  2. Check original color.
  3. Replace color.
  4. Visit 4 directions.

Practice

Complexity Analysis

DFSTime Complexity: O(m × n)
Space Complexity: O(m × n)

BFS
Time Complexity: O(m × n)
Space Complexity: O(m × n)

Why This Problem is Important

  • BFS
  • DFS
  • Matrix Traversal
  • Connected Components
  • Graph Traversal

Common Beginner Mistakes

  • Forgetting original color
  • Infinite recursion
  • Boundary errors
  • Recoloring wrong cells
  • Missing same-color check

Interview Tip

Always explain:

Visit only cells having the original color.

Then recolor and continue DFS/BFS.

Related Questions

  • Number of Islands
  • Surrounded Regions
  • Pacific Atlantic Water Flow
  • Rotting Oranges
  • Walls and Gates

Final Takeaway

Flood Fill is one of the easiest and most important BFS/DFS grid problems.

It teaches:

  • Matrix Traversal
  • DFS
  • BFS
  • Connected Components

Mastering Flood Fill makes most grid-based traversal questions much easier to solve.