Number of Enclaves
Understanding the Problem
We have a 2D grid of 0s and 1s. A land cell (1) that can reach the grid boundary through a chain of 4-directionally adjacent land cells can walk off the grid, so it is not an enclave. We count the land cells that have no such path, the ones completely surrounded by sea or by the edge they cannot reach.
A useful way to frame this: flood water inward from all four edges. Any land cell the water reaches, starting from boundary land cells and spreading through connected land, can escape and is not an enclave. The land that stays dry is what we count.
This is the same core idea as "Surrounded Regions" (LeetCode #130), where surrounded O's get flipped to X's: identify what connects to the boundary, and everything else is enclosed.
Key Constraints:
1 <= m, n <= 500→ The grid holds up to 250,000 cells. An O(m * n) traversal handles this in well under a second. The enclave count fits in a 32-bitint, so no overflow concern.grid[i][j] is 0 or 1→ A binary land/sea grid, so a single visited marker per cell is enough.
Approach 1: Brute Force (DFS from Every Land Cell)
Intuition
Process the grid one connected component at a time. From each unvisited land cell, run a DFS that explores its entire component and records two things: every cell in the component, and whether any of those cells sits on the grid boundary.
If the component touches the boundary, every cell in it can walk off the grid, so none are enclaves. If the component never touches the boundary, it is fully enclosed, so all of its cells are enclaves and we add the component size to the count.
A global visited array keeps each component processed once. Without it, starting a fresh DFS from a second cell in an already-explored component would redo the same work.
Algorithm
- For each cell (i, j) in the grid where
grid[i][j] == 1: - Run a DFS/BFS from (i, j), tracking all visited cells in this traversal.
- During the traversal, check if any visited cell is on the boundary.
- If no boundary cell is reached, add the size of the component to the enclave count.
- Use a global visited array to avoid counting the same component twice.
- Return the total enclave count.
Example Walkthrough
Code
- Time Complexity: O(m n). We visit each cell at most once thanks to the visited array. Each cell's DFS does O(1) work (checking 4 neighbors). So across all cells, total work is O(m n).
- Space Complexity: O(m n). The visited array takes O(m n) space. The component list and recursion stack can also grow up to O(m * n) in the worst case.
Tracking component membership and a boundary flag for each component is more bookkeeping than the problem needs. The next approach eliminates all boundary-connected land in a single sweep and then counts whatever land remains.
Approach 2: Boundary DFS (Flood Fill from Edges)
Intuition
Instead of asking whether each land cell can escape, flip the perspective and start from the boundary, working inward.
Walk along all four edges. Whenever an edge cell holds a 1, run a DFS from it and sink every connected land cell by changing its value from 1 to 0. After every boundary land cell is processed, the only 1s left are land cells that no boundary cell could reach. Those are the enclaves, found by a single counting pass over the grid.
This splits the work into two passes: erase boundary-connected land, then count what survives. No per-component bookkeeping is needed.
A land cell can walk off the grid if and only if it lies in a component that contains at least one boundary cell. Reachability through adjacent land is symmetric, so if any cell in a component can reach the boundary, all of them can, and if none touches the boundary, none can escape. Starting a DFS from every boundary land cell sinks exactly the escapable components. Every 1 left behind belongs to a component with no boundary cell, which is the definition of an enclave.
Setting visited cells to 0 does double duty: it prevents revisiting a cell during the flood, and it removes that cell from the grid so the final pass counts only enclaves.
Algorithm
- Walk along all four edges of the grid (first row, last row, first column, last column).
- For each boundary cell that contains a 1, run a DFS that changes all connected 1s to 0.
- After all boundary DFS traversals complete, scan the entire grid.
- Count and return the number of remaining 1s.
Example Walkthrough
Code
- Time Complexity: O(m n). The boundary scan is O(m + n). Each DFS visit marks a cell, and no cell is visited more than once. The final counting pass is O(m n). Total: O(m * n).
- Space Complexity: O(m n). The recursion stack can grow up to O(m n) in the worst case (e.g., a grid that's entirely land). No extra data structures beyond the call stack.
The boundary DFS is optimal in time and space, but recursive DFS can overflow the call stack on large grids. An iterative traversal removes that risk.
Approach 3: BFS from Boundary (Iterative)
Intuition
The algorithm matches Approach 2, but the flood uses BFS instead of recursion. Collect every boundary land cell into a queue and sink it. Then, while the queue is non-empty, dequeue a cell and enqueue any land neighbor, sinking each neighbor as it is added. When the queue drains, the remaining 1s are the enclaves.
The queue lives on the heap, so the traversal depth is no longer bounded by the call stack. For a 500 x 500 grid of all 1s, the recursive flood would nest 250,000 frames deep and overflow the stack in most languages. The iterative version holds those cells in the queue instead.
Algorithm
- Create a queue. Scan all four boundaries and enqueue every cell where
grid[i][j] == 1. Mark each enqueued cell by setting it to 0. - While the queue is not empty:
- Dequeue a cell (r, c).
- For each of its 4 neighbors, if the neighbor is in bounds and is a 1, set it to 0 and enqueue it.
- After the queue empties, count all remaining 1s in the grid.
- Return the count.
Example Walkthrough
Code
- Time Complexity: O(m n). We scan the boundary in O(m + n), the BFS visits each cell at most once in O(m n), and the final count is O(m * n).
- Space Complexity: O(m n). The queue can hold up to O(m n) cells in the worst case (if most of the grid is boundary-connected land).
The graph-traversal approaches solve this directly. Union Find offers a different lens, treating the grid as a set of cells that merge into connected groups, which is the standard tool when the underlying question is about connectivity.
Approach 4: Union Find
Intuition
Model connectivity explicitly. Add one virtual node that represents "off the grid." Union every boundary land cell with this virtual node, and union every pair of horizontally or vertically adjacent land cells. After all unions, two cells share a set exactly when they belong to the same component.
A land cell can escape if and only if its set contains the virtual node. So the enclaves are the land cells whose representative differs from the virtual node's representative.
To avoid unioning each adjacency twice, look only at the right and down neighbor of each cell. The left and up adjacencies are covered when those neighbors are processed.
Algorithm
- Create a disjoint-set structure over
m * ncell nodes plus one extra virtual node with indexm * n. - Scan every cell. For each land cell:
- If it lies on the boundary, union it with the virtual node.
- Union it with its right neighbor and its down neighbor when those are land.
- Find the virtual node's representative.
- Count land cells whose representative is not the virtual node's representative. Return that count.
Example Walkthrough
Code
- Time Complexity: O(m n α(m n)), where α is the inverse Ackermann function from path compression and union by size. With both optimizations α is effectively a small constant, so this is O(m n) in practice.
- Space Complexity: O(m n). The parent and size arrays each hold m n + 1 entries. There is no recursion, so no call-stack cost.
The boundary BFS in Approach 3 is the most practical choice: O(m n) time, O(m n) space, no recursion, and a small constant factor. Union Find reaches the same complexity bound but carries a heavier constant and more code, so prefer it only when connectivity queries are part of a larger problem.