Day 9 - Flood Fill

🧩 Problem:

Given an m x n image grid (List[List[int]]), a start coordinate (sr, sc), and a color, implement a flood fill algorithm starting from that pixel.

Flood fill means:

• Change the color of the starting pixel

• Recursively change the color of adjacent pixels (up/down/left/right) if they match the original color

Return the modified image.

🧪 Examples:

Example 1
Input:
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]]

Example 2
Input:
image = [[0,0,0],[0,0,0]]
sr = 0, sc = 0, color = 0
Output:
[[0,0,0],[0,0,0]]
(Already filled with the target color—no action needed.)

📏 Constraints:

• 1 <= m, n <= 50

• 0 <= image[i][j], color < 2^16

• 0 <= sr < m

• 0 <= sc < n

🧠 How to Approach It

This is a DFS grid traversal problem:

• Save the original color

• Create a helper DFS function to recursively visit valid neighbors

• Base case: out-of-bounds or different color

• Edge case: if the original color is already equal to the target color, do nothing

✅ Python Solution:

class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
        original_color = image[sr][sc]
        if original_color == color:
            return image
        
        def dfs(r, c):
            if (r < 0 or r >= len(image) or 
                c < 0 or c >= len(image[0]) or 
                image[r][c] != original_color):
                return
            
            image[r][c] = color
            dfs(r + 1, c)
            dfs(r - 1, c)
            dfs(r, c + 1)
            dfs(r, c - 1)
        
        dfs(sr, sc)
        return image

💬 TL;DR:

This is a core grid DFS problem, similar to:

• Island counting

• Maze solving

• Image manipulation

Once you understand how to navigate a grid recursively, these types of problems become second nature.