Flood Fill

Image Grid

Current Cell

Original Color

New Color

Queue Size

BFS Queue

Empty

Click "Step" or "Play" to start the visualization

Original Color

New Color

Current

In Queue

Python Code - BFS Approach

                original_color = image[sr][sc]
            
                queue = deque([(sr, sc)])
            
                while len(queue) > 0:
            
                    i, j = queue.popleft()
            
                    if in_bounds(i, j) and image[i][j] == original_color:
            
                        if not visited[i][j]:
            
                            visited[i][j] = True
            
                            image[i][j] = color # fill with new color
            
                            for di, dj in directions:
            
                                queue.append((i+di, j+dj))

Complexity Analysis

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

Time Complexity: O(m × n)

Breakdown

Each cell visited at most once
4 neighbors checked per cell: O(1)
Color change operation: O(1)
Worst case: entire grid is same color

T(m,n) = O(m × n) cells × O(1) work = O(m × n)

Mathematical Intuition

Flood fill is a connected component traversal. BFS explores cells in "wavefront" order—all cells at distance d from source are processed before distance d+1. The visited check (or immediate color change) ensures each cell enters the queue exactly once.

Key Insight

DFS and BFS have identical time complexity here. BFS may be preferable for very large connected regions to avoid stack overflow.

Space Complexity: O(m × n)

Breakdown

BFS queue: O(m × n) worst case
DFS recursion stack: O(m × n) worst case
Visited tracking: O(1) if using color change
Typical case: O(perimeter) queue size

S(m,n) = O(m × n) for queue/stack storage

Mathematical Intuition

The queue size at any moment equals the "frontier"—cells discovered but not yet processed. For BFS, this is bounded by the largest wavefront, which can approach O(m × n) for certain shapes. In practice, the frontier is often O(min(m, n)).

Key Insight

Changing the color in-place serves as the visited marker—no separate visited array needed, but the original image is modified.