STEP 15 · GRAPHS · THE PAINT IS THE VISITED-MARK · EASY

Flood Fill

WHAT IT SAYS

Starting from a given pixel, recolour it and every pixel connected to it through same-coloured neighbours.

WHAT IT'S REALLY ASKING

"The region to fill is defined by reachability — same colour, touching, transitively. That's a traversal, and here's the economy: the act of PAINTING a pixel is also the act of marking it visited, because a painted pixel no longer matches the old colour and the traversal's own entry test rejects it. The mutation you were asked to perform doubles as the bookkeeping you'd otherwise build."

THE INSIGHT LADDER — FROM BRUTE FORCE TO OPTIMAL

Traverse with a separate visited matrix

O(m·n) time, O(m·n) extra space for the visited structure

Standard DFS/BFS from the seed: expand into 4-neighbours that share the original colour and aren't in a visited set; paint each visited cell the new colour.

WHERE THE WORK IS WASTED — The visited matrix records one bit per cell — 'have I been here?' — but the grid itself already records it, for free: a processed cell HOLDS THE NEW COLOUR, and the traversal's entry condition ('does this cell match the old colour?') already distinguishes painted from unpainted. The auxiliary matrix duplicates information the mutation writes anyway. Harmless-looking, but it doubles memory on huge images and, more tellingly, it signals a missed reading of the problem: this is one of those tasks where the OUTPUT is a valid marker, and building separate bookkeeping means paying twice for one bit.

KEY OBSERVATION — THE UNLOCKlink

Painting a cell removes it from its own frontier test.

The region is precisely the connected component of the seed in the implicit graph whose nodes are cells of the seed's ORIGINAL colour and whose edges join 4-adjacent cells. Any component traversal fills it: from the seed, expand into neighbours matching the old colour, paint on arrival. The elegant closure: after painting, a cell fails the 'matches old colour' test — the exact test the traversal uses to decide expansion. So the mutation is self-limiting; no visited set is needed because the traversal cannot re-enter territory it has already transformed. Output-as-marker, the same species of trick as sinking islands ('1'→'0') — whenever the required mutation makes a cell unrecognisable to the entry test, the bookkeeping is free. Now the edge case that is really a correctness proof of the above: if the NEW colour equals the OLD colour, painting changes nothing, the entry test keeps matching, and the traversal orbits forever — infinite loop, stack overflow. The guard is one comparison up front (old == new: return immediately, the fill is a no-op). This isn't pedantry; it's the demonstration that the visited-mechanism WAS the paint. Remove the paint's effect and the traversal loses its memory. Any interviewer probing this problem is probing for exactly this case, because it proves you understood where the visited-bit was hiding. DFS versus BFS is genuinely a matter of indifference for correctness here — the region gets consumed either way — but not for robustness: a large single-colour image makes the recursion as deep as the region is long (a snake of a million pixels = a million frames), so production code uses an explicit stack or queue. Recursion's elegance is rented from the OS stack, and images are exactly the input class that calls the loan.

Guard the no-op, then traverse painting on entry

O(m·n) time worst case, O(1) extra space beyond the traversal frontier

If image[sr][sc] equals the new colour, return the image unchanged. Otherwise record old = image[sr][sc], and DFS/BFS: paint the cell, then expand into in-bounds 4-neighbours whose colour equals old. Iterative stack/queue preferred for depth safety.

WHAT YOU TRADED — Output-as-marker saves the visited structure but couples correctness to the mutation — if the problem ever changes to 'return the region WITHOUT modifying the image', the visited set returns from exile; and the equal-colours guard is a permanent tax on the trick. The transferable lesson: before allocating visited-bookkeeping, check whether the transformation you're already performing makes processed elements fail the entry test — when it does, the output is the visited set.

WATCH THE IDEA RUN

1seed

visited set none — the paint IS the mark

cells painted 0

The obvious implementation carries a visited set alongside the image. Look closely at what the paint itself is already doing.

step 1 / 20

THE PATTERN — SO YOU RECOGNIZE IT NEXT TIME

Output as Visited-Mark

YOU'LL SEE IT AGAIN WHEN

The task mutates each processed element (paint, sink, consume), and the mutation makes it fail the traversal's own expansion test.
The no-op input (new state equals old state) breaks the self-limiting property — a mandatory guard, and the proof you saw the mechanism.
The region is a connected component under 'same value + adjacent' — pure reachability, no distances, so DFS and BFS are interchangeable.

SAME BLUEPRINT, DIFFERENT PROBLEM

Number of Islands (sinking as the same trick)Surrounded RegionsColoring A BorderIsland Perimeter

The bar isn't "solved it once." It's "could rebuild it from the observation."