The Flood Fill Problem

Why do I even have that image? Nevermind xD

If you’ve ever messed around with MS Paint and used the bucket tool, you’ve already used a concept called flood fill.

It’s that moment when you click on a colour, and it spreads across the connected area like magic.

Simple, right? Well, coding that behaviour is a different story :)

Recently, I asked someone the Easy Flood Fill problem (From LeetCode), and as the candidate was solving it, It got me thinking about how deceptively tricky recursion can be.

So, I thought I’d share the solution and explain how it actually works — without the jargon overload.

The Problem in Simple Words

You’re given an image represented by a 2D grid where each number is a colour. You also have a starting pixel (row and column index) and a new colour.

The task? Replace the colour of the starting pixel and all connected pixels (up, down, left, right) that share the same original colour.

Here’s a quick example:

image = [
 [1, 1, 1],
 [1, 1, 0],
 [1, 0, 1]
]
sr, sc = 1, 1
color = 2

And after flood-filling, you’d expect this:

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

The goal is to flood the connected region with the new colour.

Sounds simple?

But recursion can be sneaky.

class Solution:
 
   def dfs(self, image, i, j, color):
     print(i, j)
     # Base conditions: Check boundaries and color match
     if i < 0 or i >= len(image):
     return
     if j < 0 or j >= len(image[0]):
     return
     if image[i][j] != self.default:
     return
     # Fill the current pixel
     image[i][j] = color
     
     # Recursive calls in four directions
     self.dfs(image, i + 1, j, color)
     self.dfs(image, i - 1, j, color)
     self.dfs(image, i, j - 1, color)
     self.dfs(image, i, j + 1, color)
   
   def floodFill(self, image, sr, sc, color):
       self.default = image[sr][sc]
       
       # If the color is already the desired color, skip
       if self.default == color:
       return image
       
       self.dfs(image, sr, sc, color)
       return image

The above is the solution. And below is breaking it down (Without the Fancy Words)

Starting Point with `floodFill`
First, I capture the original colour of the starting pixel with this line:

self.default = image[sr][sc]

Why? Because I need to know which colour to replace.

3. Next, I add this little check:

if self.default == color:
 return image

It’s a simple optimization. If the starting colour is already the new colour, there’s nothing to change — just return the original image.

4. Finally, I kick off the recursive DFS process:

self.dfs(image, sr, sc, color)

5. The Heart of the Code: The `dfs` Function

**Base Conditions**
The first three `if` statements are like security guards. They check:
1. Are we outside the grid?
2. Have we hit a pixel that isn’t the original colour?
If either is true, the recursion stops right there. No drama, no errors.
**Colour Fill**
If we pass all the checks, we fill the current pixel with the new colour:
**Recursive Exploration**
Then, we explore the neighbouring pixels in all four directions: up, down, left, and right.

self.dfs(image, i + 1, j, color) # Down
self.dfs(image, i - 1, j, color) # Up
self.dfs(image, i, j - 1, color) # Left
self.dfs(image, i, j + 1, color) # Right

This is what makes the algorithm “spread” like paint.

⚡ Why the Base Conditions Matter

Without the base conditions, things could get messy fast. Imagine recursion running wild, trying to access pixels outside the grid, or revisiting the same pixels over and over. That’s how you end up with stack overflow errors and bugs that make you question your life choices.

These checks keep the recursion clean and efficient. They stop unnecessary work and prevent errors.

⏳ What About Time Complexity?

Let’s be real: understanding time complexity isn’t always fun, but it’s important.

Time Complexity:O(N × M)
— Each pixel is visited once. So, if the grid has `N` rows and `M` columns, that’s `N × M` in total.

Space Complexity:O(N × M)
— That’s because of the recursion stack. In the worst case (like if all pixels are the same colour), the stack could grow as large as the grid itself.

🐍 Common Mistakes (That You Definitely Wouldn’t Make… Okay, Maybe You Might)

1. Forgetting Base Conditions
— Trust me, skipping these checks will crash your code in seconds.

2. Not Handling the Same Colour Edge Case
— If the new colour is the same as the original, the recursion will loop infinitely. Always check for this first.

3. Stack Overflow Errors
— Python has a recursion depth limit (default is 1000). Large images can break this. If you’re hitting this wall, consider switching to an iterative BFS approach.

In case we are meeting for the first time, come over here, it’ll be worth the roller coaster of articles that are gonna come up in the next few weeks.

Use this to get to know more about me — https://linktr.ee/shashwat_writes