Q&A

What is the Flood Fill algorithm?

By AlgoInsight Team2026-06-07algorithmsdata-structuresrecursion

Overview

Given a 2-D grid, a starting cell, and a new color, flood fill changes the start cell and every connected cell of the same original color to the new color. "Connected" usually means 4-directionally adjacent (up/down/left/right), sometimes 8-directionally (including diagonals). It's the engine behind paint-bucket tools, the "expand selection" in image editors, and region-counting problems.

graph TD
    A[Seed cell + new color] --> B[Record original color]
    B --> C{Visit a cell}
    C --> D{Same as original color<br/>and in bounds?}
    D -->|yes| E[Recolor it, enqueue/recurse neighbors]
    D -->|no| F[Stop on this branch]
    E --> C
    C -->|all done| G[Connected region filled]
    style E fill:#1e1b4b,color:#fff

DFS (Recursive) Implementation

def flood_fill(grid, sr, sc, new_color):
    original = grid[sr][sc]
    if original == new_color:
        return grid                      # nothing to do (avoids infinite loop)
    rows, cols = len(grid), len(grid[0])

    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return
        if grid[r][c] != original:
            return                        # different color → boundary
        grid[r][c] = new_color            # recolor
        dfs(r + 1, c); dfs(r - 1, c)      # 4 directions
        dfs(r, c + 1); dfs(r, c - 1)

    dfs(sr, sc)
    return grid

The two guards - bounds check and "matches original color" - define the region's edges. Note the critical early return when original == new_color, which prevents infinite recursion.

BFS (Queue) Implementation

For large regions, BFS avoids deep recursion (and stack overflow):

from collections import deque

def flood_fill_bfs(grid, sr, sc, new_color):
    original = grid[sr][sc]
    if original == new_color:
        return grid
    rows, cols = len(grid), len(grid[0])
    queue = deque([(sr, sc)])
    grid[sr][sc] = new_color
    while queue:
        r, c = queue.popleft()
        for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == original:
                grid[nr][nc] = new_color
                queue.append((nr, nc))
    return grid

Example

Start grid (fill from (1,1) with 2):     Result:
1 1 1                                     2 2 2
1 1 0                                     2 2 0
1 0 1                                     2 0 1

The connected block of 1s reachable from (1,1) becomes 2; the isolated 1 at (2,2) and the 0s are untouched.

Complexity

• Time: O(rows × cols) worst case - each cell visited at most once.
• Space: O(rows × cols) for the recursion stack (DFS) or queue (BFS) in the worst case.

4-Connectivity vs 8-Connectivity

Add the four diagonal directions for 8-connectivity:

[(1,0),(-1,0),(0,1),(0,-1),(1,1),(1,-1),(-1,1),(-1,-1)]

Clarify which connectivity is intended - it changes which regions are "connected."

Related Problems

The same traversal solves "number of islands," "surrounded regions," "max area of island," and image segmentation - all are flood fill / connected-component variants. Recognizing a problem as flood fill is often the key insight.

Why This Matters in Interviews

Flood fill is a common grid/DFS-BFS interview problem (LeetCode "Flood Fill," "Number of Islands"). Interviewers look for: correct boundary conditions (bounds + color match), the crucial original == new_color guard to avoid infinite loops, and the choice between recursive DFS (simple) and iterative BFS (no stack overflow on huge grids). Connecting it to connected-components problems shows pattern recognition.

Common Pitfalls

• Infinite loop when new_color == original and you don't short-circuit.
• Missing bounds checks → index errors.
• Stack overflow with deep recursion on very large regions (use BFS).
• Comparing against the new color mid-fill instead of the recorded original color.

References

• Flood fill: https://en.wikipedia.org/wiki/Flood_fill
• LeetCode 733 "Flood Fill": https://leetcode.com/problems/flood-fill/

More answers