STEP 15 · GRAPHS · COMPUTE THE COMPLEMENT · MEDIUM

Surrounded Regions

WHAT IT SAYS

Flip every region of O's that is completely surrounded by X's; regions touching the board's edge survive.

WHAT IT'S REALLY ASKING

"Proving a region IS surrounded means proving a negative — no escape route exists anywhere along its whole boundary. Proving a region is NOT surrounded takes one witness: it touches the border. Negatives are hard, witnesses are easy — so find the survivors instead. Everything the border can reach is safe; everything else flips by elimination."

THE INSIGHT LADDER — FROM BRUTE FORCE TO OPTIMAL

Test each region for surroundedness directly

O(m·n) time in aggregate — but two passes per region and a buffered verdict

Find each connected region of O's; traverse it fully while watching for any cell on the board's edge. If the traversal completes without touching the edge, the region is surrounded — flip it (requiring either a second pass over the region or a recorded cell list).

WHERE THE WORK IS WASTED — Structurally backwards in a way that breeds bugs: the verdict ('surrounded or not') is only known AFTER a region's traversal completes, so the flip must be deferred — buffer every cell, or re-traverse on conviction — and the traversal must carry a mutable 'escaped' flag threaded through the recursion, exactly the kind of state that gets half-reset between regions. All of it stems from asking the universally-quantified question ('does NO cell of mine touch the border?'), whose answer requires exhausting the region before acting. The existentially-quantified complement ('does the border reach me?') acts the moment it touches anything.

KEY OBSERVATION — THE UNLOCKlink

Surrounded is a negative. Escape is a witness — chase it.

Characterise the survivors: a region of O's escapes flipping if and only if it contains at least one border cell — because the only way to not be enclosed by X's is to run off the edge of the board, and connectivity carries that escape to the entire region. Now read the quantifiers. 'Surrounded' is a for-all claim (every boundary is sealed): verifying it requires inspecting everything, and no partial evidence suffices. 'Escapes' is a there-exists claim: one border contact convicts, immediately. Whenever a problem asks you to certify the for-all set, check whether the there-exists complement is cheaper — here it is drastically cheaper, because the witnesses are HANDED to you: the border cells themselves. So invert the computation's direction. Instead of asking each interior region 'can you get out?', ask the border 'what can you touch?': launch a traversal from every O on the edge, marking everything reached with a temporary symbol, say T. This is flood fill seeded at the frontier, and it computes, in one sweep, the union of ALL escaping regions — no per-region verdicts, no deferred flips, no escape flags, because safety is established at first contact and recorded in place. The finale is a single unconditional sweep, and its logic is trichotomy: every cell is now X (was always a wall), T (proven safe — restore to O), or O (an O that border-fill NEVER reached — which is precisely the definition of surrounded — flip to X). The elimination is airtight because the fill was exhaustive over escapes: any O still unmarked had no path to any border O, else the fill would have consumed it. Note the family resemblance and the difference: flood fill used the output-mutation as its visited mark; here the temporary T plays that role, needed because both final values (O and X) already mean something else. A three-symbol alphabet is the price of in-place bookkeeping when both output states are taken.

Fill from the border, then sweep the trichotomy

O(m·n) time — border fill plus one sweep — O(m·n) worst-case frontier

For every border cell containing O, flood-fill (DFS/BFS) marking reached O's as T. Then one full-grid pass: T becomes O, O becomes X, X stays. Iterative traversal preferred — a serpentine region can be m·n cells deep.

WHAT YOU TRADED — The complement approach spends a third symbol (or a separate visited array when mutation is forbidden) and requires the final rewrite pass — trivially cheap — in exchange for eliminating per-region verdicts, deferred flips, and escape-flag state entirely. The transferable lesson: when certifying 'fully enclosed / never reaches / no path exists' (a universal), compute the existential complement from its natural seeds — the border, the exits, the targets — and let elimination classify the rest. Provable negatives are usually the complement of findable positives.

WATCH THE IDEA RUN

escaped (border-reachable) 0

captured (by subtraction) 0

'Surrounded' is a property you can only confirm by failing to find an escape — you must check the WHOLE region and come back empty-handed. Negatives are expensive. Positives are cheap.

step 1 / 10

THE PATTERN — SO YOU RECOGNIZE IT NEXT TIME

Certify by Complement

YOU'LL SEE IT AGAIN WHEN

The wanted set is defined by a universal negative — 'no escape', 'never reaches the edge' — which requires exhaustion to verify directly.
The complement is defined by a witness — one border contact, one exit path — and its seeds are explicitly available (the boundary itself).
One traversal from the seeds classifies everything: marked means witnessed, unmarked means the negative holds by elimination.

SAME BLUEPRINT, DIFFERENT PROBLEM

Number of Enclaves (the counting twin of this exact inversion)Pacific Atlantic Water Flow (two complements intersected)Flood Fill (the engine underneath)Escape a Large Maze

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