STEP 15 · GRAPHS · TOTAL MINUS THE REACHABLE · MEDIUM

Number of Enclaves

WHAT IT SAYS

Count the land cells from which you cannot walk off the boundary of the grid.

WHAT IT'S REALLY ASKING

"Trapped land = all land minus escapable land — and escapable land is one flood fill from the border. When a count is over a hard-to-verify set, don't count its members one by one; count the easy complement and subtract. The border walk you'd do anyway becomes the entire algorithm, with arithmetic doing the rest."

THE INSIGHT LADDER — FROM BRUTE FORCE TO OPTIMAL

Per-region escape trials

O(m·n) aggregate — but with per-region verdict state and size accumulators

Identify each connected land region; traverse it while checking whether any of its cells lies on the border. Regions that never touch the border contribute their full size to the answer; sum those sizes.

WHERE THE WORK IS WASTED — Every region pays for a trial it may not need: interior regions get fully traversed AND fully counted, border-touching regions get fully traversed only to have their count discarded — and each traversal drags along two pieces of deferred state (an escaped flag and a running size) whose interplay is the bug surface: count-then-cancel, or flag-then-skip, either way the verdict arrives after the work. The question 'how big is the trapped set?' is being answered by interrogating each candidate individually, when a single subtraction — total land minus escaping land — answers it wholesale, with the escaping set computable from seeds the problem hands you free of charge.

KEY OBSERVATION — THE UNLOCKlink

Count the complement once; subtraction does the counting.

The identity that dissolves the problem: enclave cells = (all land cells) − (land cells reachable from the border). It holds because 'can walk off the grid' and 'connected to some border land cell' are the same property — a walk off the edge must pass through a border cell, and connectivity carries escape to every cell of a region. So the trapped set is exactly the complement, within land, of the border-reachable set. Both terms on the right are cheap in a way the left side is not. Total land: one scan, one counter — no structure at all. Border-reachable land: one multi-seed flood fill launched from every land cell on the edge, sinking (or marking) everything it touches — the Surrounded Regions engine, reused verbatim. Neither term involves per-region verdicts; neither defers anything. Two orderings of the arithmetic, equally valid, choose by taste: (a) count all land first, then flood-sink from the border while decrementing the counter per sunk cell — the counter IS the answer when the fill finishes; (b) flood-sink from the border first (no counting), then scan and count surviving land — survivors are enclaves by elimination. Version (b) is two clean phases with zero shared state, which is its argument. The deeper habit, stated once for this pair of problems: Surrounded Regions asked WHICH cells are trapped (a classification, needing the trichotomy sweep); Enclaves asks HOW MANY (a measure). Measures unlock the subtraction shortcut — you never need to identify the trapped cells individually, only to size their complement — which is why (a) can finish without ever knowing where a single enclave is. When a problem downgrades from 'find them' to 'count them', check whether |A| = |U| − |Aᶜ| lets the easy complement carry the whole computation.

Sink from the border, count what remains

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

For each border cell holding land, flood fill (iterative DFS/BFS) turning reached land to water. Then one sweep counting land cells — each survivor is provably unreachable from the border. Or: pre-count land, decrement during the sink, return the counter.

WHAT YOU TRADED — Sinking mutates the input (restore or copy if forbidden — a visited array re-enters at O(m·n) space), and the subtraction approach surrenders any per-region information: if a follow-up asks for the LARGEST enclave or their count as regions, the per-region traversal returns with its accumulators. The transferable lesson: counting questions over 'cannot reach' sets should be answered as total minus reachable — one propagation from the free seeds, one subtraction, and the universal negative is never verified directly for any element.

WATCH THE IDEA RUN

total land 7

escapable 0

enclaves = total − escapable …

Total land is 7 cells. We want the ones that can never walk off the board — and, as always, 'can never' is the expensive direction.

step 1 / 6

THE PATTERN — SO YOU RECOGNIZE IT NEXT TIME

Size the Complement, Subtract

YOU'LL SEE IT AGAIN WHEN

The question asks for a COUNT (not identification) over a set defined by unreachability — a universal negative per element.
The complement set is one propagation from explicitly given seeds (border cells, exits), making its size nearly free.
Per-region trials would compute sizes and verdicts separately, then reconcile — deferred state the subtraction never needs.

SAME BLUEPRINT, DIFFERENT PROBLEM

Surrounded Regions (the classification twin — same fill, different deliverable)Number of Closed Islands (the same count, inverted colours)Pacific Atlantic Water FlowCount Sub Islands

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