Flood Fill — Recursive DFS Paint Bucket Algorithm (LC 733)

Problem Statement#

LeetCode 733 — Flood Fill (Easy). Given an image as a 2-D integer array, a starting pixel (sr, sc), and a target colour, replace the colour of the starting pixel and all 4-directionally connected pixels of the same original colour.

Constraints:

• 1 <= m, n <= 50
• 0 <= image[i][j], color < 2^16
• 0 <= sr < m, 0 <= sc < n

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

Why This Problem Matters#

Flood Fill is the classic on-ramp for grid DFS. Keywords: "Flood Fill DFS", "LeetCode 733", "paint bucket algorithm", "graph traversal warmup". Amazon and Google use it as an early-loop warm-up before harder grid problems. If you can write this without bugs, you have proven you understand recursion, bounds, and visited tracking.

The Core Insight#

The starting cell defines the only colour we care about. From there, every neighbouring cell that matches the original colour becomes part of the flood. We mutate cells to the new colour as we visit them — that doubles as the visited mark, as long as the new colour differs from the original.

Visual Dry Run#

For image = [[1,1,1],[1,1,0],[1,0,1]] starting at (1,1) with color=2:

Solution (Optimal)#

class Solution:
    def floodFill(self, image, sr, sc, color):
        original = image[sr][sc]
        if original == color:
            return image
        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
            dfs(r + 1, c)
            dfs(r - 1, c)
            dfs(r, c + 1)
            dfs(r, c - 1)
 
        dfs(sr, sc)
        return image

var floodFill = function(image, sr, sc, color) {
    const original = image[sr][sc];
    if (original === color) return image;
    const rows = image.length, cols = image[0].length;
 
    const dfs = (r, c) => {
        if (r < 0 || r >= rows || c < 0 || c >= cols) return;
        if (image[r][c] !== original) 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;
};

Time: O(m * n) — each cell visited at most once. Space: O(m * n) recursion stack worst case (a snaking path).

Common Mistakes#

• Forgetting the early exit when original == color causes infinite recursion.
• Reading image[sr][sc] after mutation, capturing the wrong original value.
• Recursing without bounds check first.
• Comparing to 1 instead of the dynamic original colour.
• Allocating a visited matrix when mutating in place is the natural approach.

Interview Tips#

• Always check the early-exit case where the new colour equals the original.
• State why mutating the cell doubles as a visited mark.
• Mention the recursion depth could be 2500 cells on a 50x50 grid — within Python and JavaScript limits.
• Offer the BFS variant if asked about iterative solutions.

Follow-up Questions#

• What if you cannot mutate the input? Hint: visited set of (r, c) tuples.
• 8-directional flood fill — add 4 diagonal directions.
• Compute the area of the flooded region. Hint: return 1 plus sum of recursive calls.
• Multi-colour replacement — replace any of several source colours.
• Implement iteratively with an explicit stack.

Key Takeaways#

• Capture the original colour before mutating any cell.
• Add an early exit when source colour equals target colour.
• Mutating to the new colour doubles as a visited mark.
• Time and space are both O(m * n).
• DFS is the shortest implementation; BFS works equally well.
• The same template solves Number of Islands and Max Area of Island.
• Always handle the trivial no-change base case first.