Flood Fill | Leetcode 733 | DFS and BFS Approach

Discover how to implement the classic “Flood Fill” algorithm on a 2D image grid using both Depth-First Search (DFS) and Breadth-First Search (BFS). Step-by-step code, explanations, and complexity analysis included for your LeetCode prep.

What the Problem Asks

LeetCode 733: Flood Fill
You’re given a 2D grid image of colors (integers), and a starting pixel (sr, sc).
Every step, you can change the color of the current pixel’s 4-directional neighbors if they match the initial color at (sr, sc).
Return the image after filling (changing) all reachable pixels to the new color.

In plain English: starting from (sr, sc), repaint every connected region of the same original color to a new color, either by diving deep (DFS) or spreading out level by level (BFS).

Common Setup

In both solutions we:

1. Check if the start pixel already has the target color. If so, we can return image immediately.
2. Make a copy of image to avoid mutating the input (optional, but shown here).
3. Record the initial_color at (sr, sc).
4. Drive our search (DFS or BFS) from (sr, sc), changing each visited pixel to color and visiting only neighbors that still have initial_color.

DFS Solution (Recursion)

from copy import deepcopy


class Solution:
    def dfs(self, i, j, new_color, initial_color, visited, rows, cols):
        if i < 0 or i >= rows or j < 0 or j >= cols:
            return
        if visited[i][j] != initial_color:
            return
        if visited[i][j] == initial_color:
            visited[i][j] = new_color
            
        self.dfs(i + 1, j, new_color, initial_color, visited, rows, cols)
        self.dfs(i, j + 1, new_color, initial_color, visited, rows, cols)
        self.dfs(i - 1, j, new_color, initial_color, visited, rows, cols)
        self.dfs(i, j - 1, new_color, initial_color, visited, rows, cols)

    def floodFill(
        self, image: List[List[int]], sr: int, sc: int, color: int
    ) -> List[List[int]]:
        if image[sr][sc] == color:
            return image
            
        visited = deepcopy(image)
        rows = len(visited)
        cols = len(visited[0])
        initial_color = visited[sr][sc]
        
        self.dfs(sr, sc, color, initial_color, visited, rows, cols)
        
        return visited

How DFS works?

1. dfs(i, j):
   • Paints (i, j) to color.
   • Recursively calls itself on any neighbor that is still initial color.
2. Call dfs(sr, sc) once to flood the entire connected region.

This is a classic recursive DFS—you go as deep as possible from each pixel, then backtrack.

BFS Solution (Using a deque)

from copy import deepcopy
from collections import deque

class Solution:
    def floodFill(
        self, image: List[List[int]], sr: int, sc: int, color: int
    ) -> List[List[int]]:
        if image[sr][sc] == color:
            return image
            
        visited = deepcopy(image)
        rows = len(visited)
        cols = len(visited[0])
        initial_color = visited[sr][sc]
        
        queue = deque()
        queue.append((sr, sc))
        
        while len(queue) != 0:
            i, j = queue.popleft()
            visited[i][j] = color
            for x, y in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
                new_i = i + x
                new_j = j + y
                if new_i < 0 or new_i >= rows or new_j < 0 or new_j >= cols:
                    continue
                if visited[new_i][new_j] != initial_color:
                    continue
                queue.append((new_i, new_j))
        return visited

How BFS works?

Initialize the queue with the start pixel and paint it.

While queue isn’t empty:

• Pop (i, j).
• For each 4-directional neighbor (ni, nj), if it’s still initial color, paint it and enqueue it.

You spread out in “waves”, ensuring every pixel at distance 1, then distance 2, etc., gets recolored.

Time & Space Complexity

• Time Complexity: O(m × n) — each pixel is visited at most once.
• Space Complexity:
  • DFS recursion: O(m × n) in the worst case (skewed region) for the call stack.
  • BFS queue: O(m × n) in the worst case if the region spans the whole grid.

Which to Use?

• DFS is concise and easy with recursion, but beware of Python’s recursion limit on large grids.
• BFS uses an explicit queue and runs in iterative fashion, safer when recursion depth might blow up.

Wrapping Up:
Flood fill is just a graph-search problem on a grid. Whether you dive deep first (DFS) or expand in waves (BFS), the core idea is the same: visit every connected pixel of the original color and repaint it. Pick the style that best matches your comfort and constraints—both work beautifully!

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.