Number of Enclaves

Number of enclaves counts land cells from which it is impossible to walk off the grid, moving only through adjacent land. Land touching the border, or connected to it, can always escape. Searching outward from each land cell to test whether it escapes would repeat enormous amounts of work. The efficient method inverts the question: - Instead of finding trapped land, find the land that can escape — flood-fill inward from every border land cell, and whatever remains is enclosed. Every cell reachable from the border escapes by definition, so one traversal per border cell marks all of them, and a final count of unmarked land gives the answer directly. So the algorithm has three phases: traverse from all border land cells, marking as you go; then scan the whole grid counting land that was never marked. Seeding must include every border cell, not just the corners. All four edges — the full first and last rows and the full first and last columns — need checking, and missing one edge leaves escapable land counted as trapped. Marking can be done by writing 0 over visited land, which removes the need for a separate visited grid. That mutates the input, which is acceptable here, and makes the final count a simple sum of remaining 1s. Recursive DFS can overflow the stack on a large grid where the land forms one long connected region. BFS or an explicit stack avoids that. Each cell is visited a constant number of times, so the cost is O(m × n) in both time and space.

The same border flood as Surrounded Regions, counting instead of rewriting. Sink every land cell reachable from the edge, then whatever land survives is enclosed. Recognising the shared shape means the second problem costs almost no new thought.