Cracking The Coding Interview Together – Problem 8.10: Paint Fill

Have you ever stared at the 'bucket fill' or 'paint fill' tool in an image editor like Photoshop and wondered how it magically floods a contiguous area of pixels without spilling over into the rest of the image? It looks simple on the surface, but when we translate this interactive feature into raw code, we enter the realm of graph traversal and matrix manipulation. As developers, we often encounter spatial problems where state needs to propagate across a grid based on specific boundary conditions.

Today, we are diving into problem 8.10 from Cracking the Coding Interview: Paint Fill. By the end of this article, you will not only have a production-ready solution in Java, but you will also understand the architectural tradeoffs between recursive and iterative traversal strategies, how to avoid stack overflows, and how to handle edge cases gracefully.

Problem Statement

Implement the 'paint fill' function that you might see on many image editing programs. That is, given a screen (represented by a two-dimensional array of colors), a point, and a new color, fill in the surrounding area until the color changes from the original color.

To make our operational goals explicit, we need to:

• Accept a 2D array of colors (which can be integers, enums, or objects).
• Accept a starting coordinate (row, column).
• Accept a target replacement color.
• Traverse and mutate all connected cells sharing the original color of the starting point, moving horizontally and vertically (and optionally diagonally, though standard paint fill is 4-way directional).
• Safely handle out-of-bound checks and prevent infinite loops when the new color matches the original color.

Analyze the Problem Together

When we first look at a grid-based problem, our minds naturally gravitate toward graph traversal algorithms like Breadth-First Search (BFS) or Depth-First Search (DFS). In computer graphics, this specific flavor of DFS or BFS is known as the Flood Fill algorithm.

Let's break down the constraints and the core conflict. The primary 'Aha!' conflict in Paint Fill is the infinite recursion trap. If the color we want to paint the screen with is identical to the original color of the starting pixel, a naive algorithm will continuously visit the same pixels, make no changes, and eventually crash our program with a StackOverflowError. We must guard against this explicitly.

Let's compare our implementation options:

Clean, concise, mirrors the spatial nature of the problem.Safe from stack overflows, processes level by level.Avoids recursion overhead while maintaining depth-first flow.

We will build a robust recursive DFS solution because of its readability and elegance, but we will add safety checks to ensure it remains production-safe.

Questions for the Interviewer

Before we write a single line of code, as senior engineers, we want to align with our interviewer on constraints and edge cases:

• Is this a 4-way or 8-way directional fill? (Standard paint fill uses 4-way: up, down, left, right).
• How are colors represented? Are we dealing with primitive integers, hex codes, or a custom Color object? (We will use integers for simplicity).
• What should happen if the coordinates are out of bounds? Should we throw an exception or silently return? (We should silently return or guard against it).
• What if the screen is null or empty? Do we throw an IllegalArgumentException?

Think About the Solution

Our solution will consist of a primary driver method, paintFill, which acts as a safety validator, and a helper method, fill, which performs the recursive traversal.

Here is our high-level architecture:

1. Validate input parameters: Ensure the screen is not null and the starting point is valid.
2. Capture the original color at the given coordinate.
3. Check if the original color is already equal to the target color. If it is, return immediately to prevent infinite recursion.
4. Invoke the recursive helper function for the current cell, which checks bounds, verifies color matches, updates the cell, and recursively calls its four neighbors.

Write Code and Explain

Here is the production-ready Java implementation for the Paint Fill algorithm:

public class PaintFillService {

    /**
     * Public driver method to initiate the paint fill operation.
     * 
     * @param screen      The 2D array representing the image/screen.
     * @param r           The starting row index.
     * @param c           The starting column index.
     * @param newColor    The color to paint the area with.
     * @return            True if the fill was performed, false otherwise.
     */
    public boolean paintFill(int[][] screen, int r, int c, int newColor) {
        // Defensive programming: check for null or empty screens
        if (screen == null || screen.length == 0 || screen[0].length == 0) {
            throw new IllegalArgumentException("Screen cannot be null or empty.");
        }

        // Validate starting coordinates
        if (r < 0 || r >= screen.length || c < 0 || c >= screen[0].length) {
            throw new IndexOutOfBoundsException("Starting coordinates are out of bounds.");
        }

        int originalColor = screen[r][c];
        
        // Optimization/Safety check: if the color is already the target, do nothing
        if (originalColor == newColor) {
            return false;
        }

        return fill(screen, r, c, originalColor, newColor);
    }

    /**
     * Recursive helper method implementing depth-first flood fill.
     */
    private boolean fill(int[][] screen, int r, int c, int originalColor, int newColor) {
        // Base case 1: Check boundaries
        if (r < 0 || r >= screen.length || c < 0 || c >= screen[0].length) {
            return false;
        }

        // Base case 2: If the current pixel's color doesn't match the original, stop
        if (screen[r][c] != originalColor) {
            return false;
        }

        // Action: Paint the current pixel
        screen[r][c] = newColor;

        // Recursive step: Traverse 4-way directions (Up, Down, Left, Right)
        fill(screen, r - 1, c, originalColor, newColor); // Up
        fill(screen, r + 1, c, originalColor, newColor); // Down
        fill(screen, r, c - 1, originalColor, newColor); // Left
        fill(screen, r, c + 1, originalColor, newColor); // Right

        return true;
    }
}

Step-by-Step Walkthrough:

• We first validate that our 2D array isn't null and that our initial coordinates fall safely within the matrix boundaries.
• We store screen[r][c] as our originalColor. This ensures we only flood pixels belonging to the contiguous region we clicked on.
• If originalColor == newColor, we short-circuit and return false. Without this check, our recursive function would visit a pixel, see that it's already the new color, try to paint it again, and recurse infinitely.
• Inside the recursive fill method, we check if our indices are out of bounds or if the current pixel has already been painted (meaning its color no longer matches originalColor). If either condition is true, we return.
• If valid, we mutate the pixel to newColor and branch out into its four orthogonal neighbors.

Time & Space Complexity

Let's analyze the algorithmic cost:

• Time Complexity: $O(V)$, where $V$ is the number of pixels in the connected component of the same color. In the worst-case scenario where the entire screen is filled with a single color, we touch every single pixel once, resulting in $O(M \times N)$ where $M$ is rows and $N$ is columns.
• Space Complexity:
• $O(V)$ in the worst-case for the recursive call stack. If the filled region forms a long winding line or snakes across the entire grid, the call stack can grow up to the number of pixels in that region, bounded by $O(M \times N)$. If stack depth is a concern in production environments, an iterative BFS queue approach can be substituted to manage memory on the heap instead of the call stack.

Why This Problem Matters (The Senior Perspective)

Flood fill algorithms are not just interview tropes; they appear everywhere in production systems. Game development uses them for map generation and territory control (think flood-filling regions in strategy games). Computer vision and image processing rely on them for blob detection and segmentation. Furthermore, distributed systems use analogous graph traversal patterns when propagating cache invalidations or cluster state changes across network topologies.

Understanding recursion limits, stack overflow vulnerabilities, and boundary validation sets senior engineers apart from juniors who simply write code that 'works on happy paths'. Always think about what happens when your data structure scales to extremes.

Final Thoughts

Mastering spatial problems like Paint Force builds vital intuition for handling multidimensional arrays and graph traversals. Remember to always look out for edge cases like infinite loops and boundary violations before writing your core logic.

Take this code, experiment with an iterative queue-based version, and see how it alters your memory footprint. Happy coding, and see you in the next breakdown!