The core approach: Flood Fill is solved with BFS or DFS in O(m×n) time and O(m×n) space. Starting from the given pixel, traverse all 4-directionally connected pixels sharing the original color and repaint them. If the starting pixel already has the new color, return immediately to avoid an infinite loop.

Flood Fill is the MS Paint bucket tool turned into an algorithm question. It’s the canonical introduction to graph traversal on a 2D grid — the same DFS/BFS pattern you’ll use in Number of Islands, Rotting Oranges, and almost every grid problem. Interviewers use it to check whether you can handle boundaries, avoid infinite loops, and navigate 4-directional movement without overcomplicating the code.

---

Already know how to solve Flood Fill? Try a Flood Fill mock interview on Intervu →

The Problem

Given a 2D grid image, a starting pixel (sr, sc), and a new color, perform a flood fill starting from (sr, sc). A flood fill changes the color of the starting pixel and all connected pixels of the same original color (4-directional: up, down, left, right).

Example

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]]

---

What Interviewers Are Actually Testing

Skill	What Interviewers Observe
Grid DFS/BFS	Can you traverse a 2D grid correctly?
Boundary checking	Do you guard against out-of-bounds access?
Infinite loop prevention	Do you handle the case where the new color equals the original?
4-directional movement	Do you enumerate all neighbors cleanly?

---

Step 1: Clarifying Questions

1. 4-directional or 8-directional connectivity? Problem specifies 4-directional (up/down/left/right, not diagonal).
2. What if the new color equals the original? Return the image unchanged — otherwise infinite recursion.
3. Can the grid be empty? Assume at least 1x1 per constraints.

---

Step 2: The Key Insight

Flood fill is DFS/BFS from a source cell, painting all reachable same-colored cells. The “visited” mechanism is implicit: once you paint a cell to the new color, it no longer matches the original color, so you won’t revisit it.

Critical edge case: If image[sr][sc] == color already, return immediately — there’s nothing to do, and recursing would cause infinite loops.

---

Step 3: Optimal Strategy

DFS (recursive):

1. Record original_color = image[sr][sc].
2. If original_color == color: return image unchanged.
3. Define a dfs(r, c) function: if out of bounds or image[r][c] != original_color, return.
4. Paint image[r][c] = color and recurse in 4 directions.

---

Python Implementation

def floodFill(image: list[list[int]], sr: int, sc: int, color: int) -> list[list[int]]:
    original = image[sr][sc]
    if original == color:
        return image  # Avoid infinite loop

    rows, cols = len(image), len(image[0])

    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return
        if image[r][c] != original:
            return
        image[r][c] = color  # Paint
        dfs(r + 1, c)
        dfs(r - 1, c)
        dfs(r, c + 1)
        dfs(r, c - 1)

    dfs(sr, sc)
    return image

BFS alternative:

from collections import deque

def floodFill(image, sr, sc, color):
    original = image[sr][sc]
    if original == color:
        return image

    rows, cols = len(image), len(image[0])
    queue = deque([(sr, sc)])
    image[sr][sc] = 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 image[nr][nc] == original:
                image[nr][nc] = color
                queue.append((nr, nc))

    return image

---

Time & Space Complexity

Aspect	Complexity
Time	O(m × n) — each cell visited at most once
Space	O(m × n) — recursion stack or queue

---

Common Interview Mistakes

1. Not handling original == color. This causes infinite recursion in DFS or an infinite loop in BFS. It’s the most common bug.

2. Checking bounds after accessing image[r][c]. Always check bounds first to avoid index errors.

3. Using 8-directional when 4 is correct. Ask explicitly — the problem says 4-directional.

4. Separate visited set. You don’t need one — the color change itself prevents revisiting. Adding one wastes space.

---

What a Strong Candidate Sounds Like

“I’ll do DFS from the starting cell. I record the original color, then recursively paint each 4-directional neighbor that has the original color. The early exit on original == color is critical — without it, the ‘paint then check’ logic would recurse infinitely. The color change itself acts as a visited marker, so no separate set is needed.”

---

Example Interview Dialogue

Interviewer: Why do you need the original == color check?

Candidate: Without it, when I paint a cell the new color, the DFS still recurses into neighbors. But since painted cells match the new color — which is the same as the original — they’ll match the original color again and be revisited. This creates infinite recursion.

Interviewer: Could you use BFS instead?

Candidate: Absolutely. The BFS version uses a queue and paints cells as they’re enqueued rather than when they’re dequeued. This prevents adding duplicates. Both are O(m×n) time and space — the choice is whether you prefer a call stack or an explicit queue.

---

Related Problems to Practice

• Number of Islands — Same grid DFS pattern, counting connected components.
• 01 Matrix — Multi-source BFS on grid.
• Course Schedule — Graph DFS/BFS on adjacency lists instead of grids.

---

Frequently Asked Questions

What graph traversal algorithms work best for Flood Fill?

You can perform Flood Fill using either Depth-First Search (DFS) via recursion or Breadth-First Search (BFS) using a Queue. Both evaluate symmetrically, hitting every adjacent pixel to color coordinate domains continuously, though DFS is often considered syntactically simpler.

What is the primary bug candidates make during a Flood Fill interview?

A massive gotcha is failing to check if the new target color matches the original color. Without this check, a cyclic graph traversal can trigger an infinite recursive stack overflow as cells endlessly repaint themselves back and forth.

Practice This in a Mock Interview

Flood Fill is a warm-up problem that tests the same grid traversal mechanics used in harder problems. Getting the edge cases right — especially the original == color check — is what separates a clean solution from a buggy one.

Start a mock interview for Flood Fill on Intervu.

---

Further reading:

• How to Prepare for a Coding Interview in 2026, the complete roadmap
• Why LeetCode alone isn’t enough, and what to practice instead
• Practice any LeetCode problem as a live mock interview
• The Grind 75 Pathway, a structured study plan with AI practice links
• Browse all walkthroughs on GitHub, condensed solutions with code