Graphs · Flood fill on a grid — the inversion LeetCode 130

Surrounded Regions / visualized

You cannot mark a cell enclosed. Enclosure is a property of a whole region, and it is only ever falsified — the moment a walk steps off the edge — never confirmed until the walk is over. Its complement is confirmable from one cell: an O on the border escapes, full stop. So invert the question. Seed the border, flood-mark everything that escapes, then flip whatever the mark did not reach.

Board — X and O, rows split by /

Where the walk starts

Execution

idle

Press Run to begin.

0 / 0

Speed

Java · running line

wall — X from the start current cell in the queue marked — it escapes captured — flipped to X

O(m·n) time · O(m·n) for the queue · the one-pass version — walk each region, remember whether it touched the border, then decide — needs a per-region list to go back and repaint, and a flag threaded through the recursion. The complement needs neither: an O on the border is known to escape from that one cell, with no region to assemble. Same O(m·n) work, none of the bookkeeping. The temporary # is the only price, and the third pass erases it.