The O(n) Club: Flood Fill (LeetCode 733): When Your Paint Bucket Actually Needs a Manual

The O(n) Club: Flood Fill (LeetCode 733): When Your Paint Bucket Actually Needs a Manual

⚡ TL;DR

You want the code version of MS Paint’s bucket tool—a way to turn a whole, boring blob of pixels into another color, but only if they’re awkwardly attached like conjoined twins (up/down/left/right, but not diagonally). Check for stack overflows, facepalm when diagonals get colored (they shouldn’t), and whatever you do, make sure you don’t flood the entire image because you forgot a base case. Java snippet incoming:

// Paint those pixels (but not your whole career)
void floodFill(int[][] image, int sr, int sc, int newColor) {
    int orig = image[sr][sc];
    if (orig == newColor) return;
    paint(image, sr, sc, orig, newColor);
}
void paint(int[][] img, int r, int c, int orig, int newCol) {
    if (r < 0 || c < 0 || r >= img.length || c >= img[0].length) return;
    if (img[r][c] != orig) return;
    img[r][c] = newCol;
    paint(img, r+1, c, orig, newCol);
    paint(img, r-1, c, orig, newCol);
    paint(img, r, c+1, orig, newCol);
    paint(img, r, c-1, orig, newCol);
}

🧠 How Devs Usually Mess This Up

Let’s be brutally honest: classic mistakes abound. Like coloring diagonals because, hey, why not? (Hint: the algorithm doesn’t care about your diagonals, only the grid’s awkward handholding.) Or “filling” without checking if the pixel is the right color, which is the digital equivalent of painting your neighbor’s house while redecorating yours. Skipping bounds checks? Prepare for a thrilling ArrayIndexOutOfBoundsException light show. And of course, there’s the infinite recursion masterpiece that makes the stack throw in the towel before your IDE does.

🔍 What’s Actually Going On

This is the Paint Bucket Tool’s origin story. Click once; it pours through every 4-directionally connected pixel matching your starting color, stopping dead at any boundary. No diagonal growth—so unless you’re living in a Picasso painting, don’t even bother checking them. We do this with DFS (because it’s easy) or BFS (if you’re traumatized by stack limits). Each time you visit, flip the pixel. If you ever forget to check if you already colored it, stuff gets wild.

🛠️ PseudoCode

• Chill check: If the pixel’s already the new color, pat yourself on the back and leave.
• Recursion party: For each neighbor (no diagonals allowed)—if it’s inside the grid and matches the original color, call yourself recursively. Yes, you’re that important now.
• Stop when you can: If you step off the board or see a different color, U-turn.

// Java-flavored pseudocode
dfs(img, row, col, orig, newCol):
    if out of bounds OR img[row][col] != orig:
        return
    img[row][col] = newCol
    dfs(up)
    dfs(down)
    dfs(left)
    dfs(right)

• Pro tip: Don’t touch diagonals unless the interviewer specifically wants abstract art.

💻 The Code

public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
    int origColor = image[sr][sc];
    if (origColor == newColor) return image;
    fill(image, sr, sc, origColor, newColor);
    return image;
}
private void fill(int[][] img, int r, int c, int orig, int newCol) {
    if (r < 0 || c < 0 || r >= img.length || c >= img[0].length) return;
    if (img[r][c] != orig) return;
    img[r][c] = newCol;
    fill(img, r + 1, c, orig, newCol); // Down
    fill(img, r - 1, c, orig, newCol); // Up
    fill(img, r, c + 1, orig, newCol); // Right
    fill(img, r, c - 1, orig, newCol); // Left
}

⚠️ Pitfalls, Traps & Runtime Smacks

• DFS Stack Slam: Recursion hates really big images. If you’re filling a 10,000×10,000 grid, expect the call stack to beg for mercy. Switch to BFS if you care about not crashing in an interview.
• Diagonal Drama: Seriously, diagonals are dead to you here. Don’t paint them unless your manager also wants a bonus bug.
• Forgot to Check Color? If you don’t check the match before painting, everything turns into a Jackson Pollock. Not good (unless you’re Jackson Pollock).
• Missing Boundaries: If you wander outside the grid, Java throws its very helpful runtime tantrum. Mind your edges.
• Complexity Check: O(n) for time and space (n = number of pixels touched). Out-of-control recursion can waste memory on big, flat regions.

🧠 Interviewer Brain-Tattoo

Flood Fill is like painting a room with perfect tape on the doors: DFS spreads color everywhere it can, but only if it fits the boring rules. No paint on ceilings. No drama in the diagonals.