Number of Enclaves Solution & Editorial - DSA Pattern

Number of Enclaves Solution & Editorial - DSA Pattern | Thita.ai

text
count = 0
visited = set()
for r in 0 to m:
    for c in 0 to n:
        if grid[r][c] == 1 and (r,c) not in visited:
            island_size, touched_boundary = dfs(r, c, visited)
            if not touched_boundary:
                count += island_size
return count

cpp
class Solution {
public:
    int numEnclaves(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        
        // Helper DFS function to mark connected lands as visited (0)
        function<void(int, int)> dfs = [&](int r, int c) {
            if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] == 0) {
                return;
            }
            grid[r][c] = 0; // Mark as visited/sea
            
            // Visit 4 directions
            dfs(r + 1, c);
            dfs(r - 1, c);
            dfs(r, c + 1);
            dfs(r, c - 1);
        };
        
        // 1. Traverse boundaries and sink connected lands
        for (int i = 0; i < m; ++i) {
            if (grid[i][0] == 1) dfs(i, 0);
            if (grid[i][n - 1] == 1) dfs(i, n - 1);
        }
        
        for (int j = 0; j < n; ++j) {
            if (grid[0][j] == 1) dfs(0, j);
            if (grid[m - 1][j] == 1) dfs(m - 1, j);
        }
        
        // 2. Count remaining land cells (enclaves)
        int enclaves = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) {
                    enclaves++;
                }
            }
        }
        
        return enclaves;
    }
};

java
class Solution {
    private int m;
    private int n;

    public int numEnclaves(int[][] grid) {
        m = grid.length;
        n = grid[0].length;

        // 1. Traverse boundaries and sink connected lands
        for (int i = 0; i < m; i++) {
            if (grid[i][0] == 1) dfs(grid, i, 0);
            if (grid[i][n - 1] == 1) dfs(grid, i, n - 1);
        }

        for (int j = 0; j < n; j++) {
            if (grid[0][j] == 1) dfs(grid, 0, j);
            if (grid[m - 1][j] == 1) dfs(grid, m - 1, j);
        }

        // 2. Count remaining land cells (enclaves)
        int enclaves = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    enclaves++;
                }
            }
        }

        return enclaves;
    }

    private void dfs(int[][] grid, int r, int c) {
        // Boundary checks and sea check
        if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] == 0) {
            return;
        }

        // Mark as visited by turning land to sea
        grid[r][c] = 0;

        // Recurse in 4 directions
        dfs(grid, r + 1, c);
        dfs(grid, r - 1, c);
        dfs(grid, r, c + 1);
        dfs(grid, r, c - 1);
    }
}

python
import sys

# Increase recursion depth for large grids
sys.setrecursionlimit(10000)

class Solution:
    def numEnclaves(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        
        def dfs(r, c):
            # Base case: out of bounds or water
            if r < 0 or r >= m or c < 0 or c >= n or grid[r][c] == 0:
                return
            
            # Mark as visited (sink the island)
            grid[r][c] = 0
            
            # Visit neighbors
            dfs(r + 1, c)
            dfs(r - 1, c)
            dfs(r, c + 1)
            dfs(r, c - 1)
            
        # 1. Traverse boundaries and sink connected lands
        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)
                
        # 2. Count remaining land cells (enclaves)
        enclaves = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    enclaves += 1
                    
        return enclaves

AI Coach Insight

Focus on the core pattern. For Number of Enclaves, identifying the Graph Traversal Patterns (DFS & BFS) is key to optimizing your solution.

Complexity Analysis

Time Complexity: $O(m \times n)$ We iterate through the boundary cells, which is $O(m + n)$ . The DFS visits each cell at most once because we mark visited cells as 0. The final count requires iterating over the entire grid once, which is $O(m \times n)$ . The dominant term is $O(m \times n)$ .
Space Complexity: $O(m \times n)$ In the worst case (a grid entirely filled with land), the recursion stack for DFS can grow to $O(m \times n)$ depth. If we used BFS with a queue, the space would be proportional to the maximum size of the frontier, typically $O (\min (m, n))$ , but DFS is standard for this pattern.

Related Patterns

The Graph DFS - Connected Components pattern used in LeetCode 1020 is highly versatile. Here is how it applies to similar problems:

LeetCode 130: Surrounded Regions: Almost identical logic. Instead of counting remaining 1s, you flip remaining 'O's to 'X's. The "boundary scan" strategy is exactly the same.
LeetCode 200: Number of Islands: This is the foundational problem. Here, you count every component (DFS trigger) rather than eliminating specific ones.
LeetCode 417: Pacific Atlantic Water Flow: Requires two separate boundary scans (one for Pacific, one for Atlantic) to find the intersection of reachable cells.
LeetCode 547: Number of Provinces: Applies the connected components logic to an adjacency matrix instead of a grid.

Common Mistakes & FAQ

Why does my solution result in a RecursionError in Python?
- Mistake: Failing to increase the recursion limit or using DFS on a very large grid (e.g., 500x500) without handling stack depth.
- Reasoning: Python's default recursion limit is usually 1000. A spiral or snake-like path of 1s in a 500x500 grid can exceed this easily.
- Consequence: The program crashes with a runtime error. Use sys.setrecursionlimit or an iterative stack-based DFS.
Why is my answer slightly off (too high)?
- Mistake: Failing to check all four boundaries.
- Reasoning: Often candidates only check rows or only check columns, forgetting that an island can touch the top/bottom just as easily as the left/right.
- Consequence: Islands connected only to the neglected boundary are incorrectly counted as enclaves.
Why do I get a Time Limit Exceeded (TLE)?
- Mistake: Not marking cells as visited (or turning 1 to 0) immediately upon entry.
- Reasoning: If you don't mark a cell as processed before recursing, the neighbors will recurse back to the current cell, creating an infinite loop or exponential re-visiting of nodes.

O(\min(m, n))

Editorial: Number of Enclaves

LeetCode 1020: Number of Enclaves Solution & Explanation

Problem Overview

Brute Force Approach for Number of Enclaves

Want to master more patterns?

Core Insight for Number of Enclaves

Execution Flow

Proof of Correctness

Reference Implementation

C++ Solution for LeetCode 1020

Java Solution for LeetCode 1020

Python Solution for LeetCode 1020

AI Coach Insight

Complexity Analysis

Related Patterns

Common Mistakes & FAQ