Problem Description

You have a grid (2D matrix) of size m x n where each cell contains either:

• 0 representing a sea/water cell
• 1 representing a land cell

From any land cell, you can walk to another land cell that is directly adjacent to it (up, down, left, or right - not diagonally). You can keep walking from land cell to land cell as long as they are connected.

The key point is that some land cells can eventually lead you to the boundary (edge) of the grid - meaning you can "walk off" the grid from them. Other land cells are completely surrounded and enclosed, meaning no matter how you walk, you cannot reach the boundary.

Your task is to count how many land cells (1s) are enclosed - that is, land cells from which it's impossible to walk off the boundary of the grid.

Example understanding:

• If a land cell is on the boundary itself, you can obviously walk off the grid from it
• If a land cell is connected (through other land cells) to a boundary land cell, you can walk off the grid from it
• Only land cells that are completely isolated from all boundary cells (surrounded by water or other enclosed land) should be counted

The solution works by:

1. Starting from all boundary land cells and marking all connected land cells as "can reach boundary" (by setting them to 0)
2. After this process, any remaining 1s in the grid are enclosed land cells
3. Counting these remaining 1s gives the answer

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: The grid can be viewed as a graph where each land cell (1) is a node, and edges exist between adjacent land cells. We need to traverse connected components of land cells.

Is it a tree?

• No: The graph formed by land cells is not a tree. It can have multiple disconnected components, and within each component, there's no hierarchical parent-child relationship.

Is the problem related to directed acyclic graphs?

• No: The problem doesn't involve directed edges or acyclic properties. The connections between land cells are undirected (you can walk in both directions).

Is the problem related to shortest paths?

• No: We're not finding shortest paths between cells. We're identifying which land cells cannot reach the boundary.

Does the problem involve connectivity?

• Yes: The core of the problem is about connectivity - determining which land cells are connected to boundary cells and which are not.

Disjoint Set Union

• While DSU could work here, the solution uses a simpler approach with DFS to mark all boundary-connected cells.

Conclusion: The flowchart leads us to connectivity problems, and the solution effectively uses DFS to explore connectivity. Starting from all boundary land cells, DFS marks all reachable land cells (setting them to 0). After this traversal, any remaining 1s are enclosed land cells that cannot reach the boundary. This is a classic application of DFS for exploring connected components in a grid graph.

Intuition

The key insight is to think about the problem in reverse. Instead of trying to identify which land cells are enclosed, we can identify which land cells can reach the boundary and then count what's left.

Think of it like water flooding in from the edges of the grid. Any land cell that touches the boundary can "escape" to the outside. Moreover, any land cell connected to a boundary land cell can also escape by walking through that path.

This suggests a natural approach:

1. Start from all land cells on the boundary (first/last row and first/last column)
2. From each boundary land cell, explore all connected land cells using DFS
3. Mark all these reachable cells as "can escape" (by setting them to 0)
4. After exploring from all boundaries, any remaining 1s must be enclosed land cells

Why does this work? Because if a land cell can reach the boundary, there must be a path of connected land cells leading to it. By starting our search from the boundary and working inward, we're guaranteed to find all such cells. The cells we never visit during this process are exactly the ones that have no path to the boundary - they're trapped inside.

The beauty of this approach is its simplicity: we convert the problem from "find enclosed cells" to "eliminate all cells that can reach the boundary, then count what remains." This transformation makes the solution straightforward - just run DFS from all boundary land cells and mark visited cells, then sum up the remaining 1s.

Learn more about Depth-First Search, Breadth-First Search and Union Find patterns.

Solution Approach

The implementation uses Depth-First Search (DFS) to mark all land cells that can reach the boundary:

1. DFS Helper Function:

def dfs(i: int, j: int):
    grid[i][j] = 0
    for a, b in pairwise(dirs):
        x, y = i + a, j + b
        if 0 <= x < m and 0 <= y < n and grid[x][y]:
            dfs(x, y)

• Marks the current cell as visited by setting it to 0
• Explores all 4 adjacent cells (up, down, left, right)
• Recursively visits unvisited land cells (grid[x][y] == 1)

2. Direction Array Setup:

dirs = (-1, 0, 1, 0, -1)

This clever pattern with pairwise() generates the 4 directions:

• pairwise(dirs) produces: (-1, 0), (0, 1), (1, 0), (0, -1)
• These represent: up, right, down, left movements

3. Process Boundary Cells:

First, process top and bottom rows:

for j in range(n):
    for i in (0, m - 1):
        if grid[i][j]:
            dfs(i, j)

Then, process left and right columns:

for i in range(m):
    for j in (0, n - 1):
        if grid[i][j]:
            dfs(i, j)

This ensures all boundary land cells and their connected components are marked as 0.

4. Count Remaining Land Cells:

return sum(sum(row) for row in grid)

After marking all boundary-connected land cells as 0, the remaining 1s are the enclosed land cells. Sum all values in the grid to get the count.

Time Complexity: O(m × n) - we visit each cell at most once Space Complexity: O(m × n) in worst case for recursion stack depth

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Consider this 4×4 grid:

1 1 1 1
1 0 0 1
1 0 0 1
1 1 1 1

Step 1: Identify boundary land cells

The boundary cells are those in the first/last row and first/last column. All boundary cells in this grid contain 1:

[1] [1] [1] [1]   <- Top row (all are 1s)
[1]  0   0  [1]   <- Left and right edges
[1]  0   0  [1]   <- Left and right edges
[1] [1] [1] [1]   <- Bottom row (all are 1s)

Step 2: Run DFS from each boundary land cell

Starting from position (0,0), the DFS will:

• Mark (0,0) as 0
• Check adjacent cells: right (0,1) and down (1,0)
• Both are land cells, so recursively visit them
• This process continues, spreading through all connected land cells

After processing the first boundary cell at (0,0), the DFS will have reached and marked all the outer ring of 1s:

0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

All land cells got marked as 0 because they form one connected component that touches the boundary.

Step 3: Count remaining 1s

Sum all values in the grid: 0 + 0 + ... + 0 = 0

There are 0 enclosed land cells in this example.

Another example with enclosed cells:

Consider this 5×5 grid:

1 1 1 1 1
1 0 1 0 1
1 0 1 0 1
1 0 0 0 1
1 1 1 1 1

Step 1: Identify boundary cells

The boundary land cells are all the 1s on the edges.

Step 2: Run DFS from boundary land cells

Starting from (0,0), DFS spreads through the outer ring. The center cell at (2,2) is surrounded by water (0s) and cannot be reached from any boundary cell.

After processing all boundary cells:

0 0 0 0 0
0 0 1 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

The 1 at position (2,2) remains because it's completely enclosed - there's no path of land cells connecting it to the boundary.

Step 3: Count remaining 1s

Sum all values: 0 + 0 + 1 + 0 + ... = 1

There is 1 enclosed land cell in this grid.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m * n) where m is the number of rows and n is the number of columns in the grid.

• The DFS function visits each cell at most once. When a cell with value 1 is visited, it's marked as 0 and never revisited.
• The boundary traversal loops iterate through all cells on the perimeter: 2m + 2n - 4 cells (avoiding corner duplicates), which is O(m + n).
• In the worst case, if all boundary cells are 1s and connected to all interior cells, the DFS could visit all m * n cells.
• The final sum operation iterates through all m * n cells once.
• Overall: O(m + n) + O(m * n) + O(m * n) = O(m * n)

Space Complexity: O(m * n) in the worst case.

• The algorithm modifies the input grid in-place, so no additional space is used for storing the grid state.
• The primary space consumption comes from the recursive call stack in DFS.
• In the worst case, if all cells are 1s and connected, the DFS recursion depth could reach m * n (imagine a spiral pattern starting from a boundary).
• The dirs tuple uses O(1) space.
• Therefore, the space complexity is O(m * n) due to the recursion stack.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Processing Boundary Cells Inefficiently or Incorrectly

Pitfall: A common mistake is to process corners twice or miss some boundary cells when iterating through the edges. For example:

# Incorrect: This processes corners multiple times
for i in range(m):
    if grid[i][0] == 1:
        dfs(i, 0)
    if grid[i][n-1] == 1:
        dfs(i, n-1)
      
for j in range(n):
    if grid[0][j] == 1:
        dfs(0, j)
    if grid[m-1][j] == 1:
        dfs(m-1, j)

Solution: Process boundaries systematically to avoid redundancy:

• First process top and bottom rows completely
• Then process left and right columns excluding corners (already processed)

# Process top and bottom rows
for col in range(cols):
    if grid[0][col] == 1:
        dfs(0, col)
    if grid[rows-1][col] == 1:
        dfs(rows-1, col)

# Process left and right columns (skip corners)
for row in range(1, rows-1):
    if grid[row][0] == 1:
        dfs(row, 0)
    if grid[row][cols-1] == 1:
        dfs(row, cols-1)

2. Modifying the Original Grid Without Permission

Pitfall: The solution modifies the input grid directly by setting cells to 0. This destroys the original data, which might be needed elsewhere or violate the problem requirements.

Solution: Create a copy of the grid or use a separate visited array:

def numEnclaves(self, grid: List[List[int]]) -> int:
    # Create a copy to preserve original
    grid_copy = [row[:] for row in grid]
  
    # Or use a visited set
    visited = set()
  
    def dfs(row, col):
        visited.add((row, col))
        for dr, dc in directions:
            new_row, new_col = row + dr, col + dc
            if (0 <= new_row < rows and 
                0 <= new_col < cols and 
                grid[new_row][new_col] == 1 and
                (new_row, new_col) not in visited):
                dfs(new_row, new_col)

3. Stack Overflow with Large Connected Components

Pitfall: Using recursive DFS can cause stack overflow for very large grids with extensive connected land masses.

Solution: Use iterative DFS with an explicit stack:

def dfs_iterative(start_row, start_col):
    stack = [(start_row, start_col)]
    while stack:
        row, col = stack.pop()
        if row < 0 or row >= rows or col < 0 or col >= cols:
            continue
        if grid[row][col] != 1:
            continue
      
        grid[row][col] = 0
        stack.extend([(row-1, col), (row+1, col), 
                     (row, col-1), (row, col+1)])

4. Forgetting Edge Cases

Pitfall: Not handling special cases like:

• Empty grid or single cell grid
• Grid with all land or all water
• Grid where all land is on the boundary

Solution: Add validation checks:

def numEnclaves(self, grid: List[List[int]]) -> int:
    if not grid or not grid[0]:
        return 0
  
    rows, cols = len(grid), len(grid[0])
  
    # Single row or column - all cells are boundary
    if rows == 1 or cols == 1:
        return 0
  
    # Continue with main logic...