Number of Enclaves

Med

#0974Time: O((m*n)²) - In the worst-case scenario, for each of the O(m*n) land cells, we might perform a traversal that visits all O(m*n) cells. This results in a quadratic time complexity.Space: O(m*n) - For each check, a `visited` matrix of size m*n is created. The queue used for BFS can also grow up to O(m*n) in the worst case.

Algorithms

Depth-First Search Breadth-First Search Union Find

Data structures

Array Matrix

Prompt

You are given an m x n binary matrix grid, where 0 represents a sea cell and 1 represents a land cell.

A move consists of walking from one land cell to another adjacent (4-directionally) land cell or walking off the boundary of the grid.

Return the number of land cells in grid for which we cannot walk off the boundary of the grid in any number of moves.

Example 1:

Input: grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
Output: 3
Explanation: There are three 1s that are enclosed by 0s, and one 1 that is not enclosed because its on the boundary.

Example 2:

Input: grid = [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
Output: 0
Explanation: All 1s are either on the boundary or can reach the boundary.

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 500
grid[i][j] is either 0 or 1.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach iterates through every cell in the grid. For each land cell (1), it performs an independent search (like Depth-First Search or Breadth-First Search) to determine if a path exists from that cell to the grid's boundary. If a cell is a land cell and no such path to the boundary can be found, it is counted as an enclave cell.

Algorithm

Initialize enclave_count = 0.
Iterate through each cell (r, c) of the grid.
If grid[r][c] is 1:
- Perform a traversal (e.g., BFS) starting from (r, c) to see if it can reach a boundary cell. This requires a new visited array for each starting cell.
- During the traversal, if any visited cell is on the boundary, we know the starting cell (r, c) can escape.
- If the entire traversal completes without finding a path to the boundary, the starting cell (r, c) is an enclave cell. Increment enclave_count.
Return enclave_count.

Walkthrough

The algorithm proceeds cell by cell. For every single land cell, we initiate a new traversal to check its connectivity to the boundary. This leads to a lot of repeated work, as cells belonging to the same island will be re-explored multiple times.

1class Solution {2    public int numEnclaves(int[][] grid) {3        int m = grid.length;4        int n = grid[0].length;5        int enclaveCount = 0;6        for (int i = 0; i < m; i++) {7            for (int j = 0; j < n; j++) {8                if (grid[i][j] == 1) {9                    if (!canReachBoundary(grid, i, j, m, n)) {10                        enclaveCount++;11                    }12                }13            }14        }15        return enclaveCount;16    }17 18    private boolean canReachBoundary(int[][] grid, int r, int c, int m, int n) {19        boolean[][] visited = new boolean[m][n];20        java.util.Queue<int[]> queue = new java.util.LinkedList<>();21        22        queue.offer(new int[]{r, c});23        visited[r][c] = true;24 25        int[] dr = {-1, 1, 0, 0};26        int[] dc = {0, 0, -1, 1};27 28        while (!queue.isEmpty()) {29            int[] cell = queue.poll();30            int row = cell[0];31            int col = cell[1];32 33            if (row == 0 || row == m - 1 || col == 0 || col == n - 1) {34                return true; // Found a path to the boundary35            }36 37            for (int i = 0; i < 4; i++) {38                int newRow = row + dr[i];39                int newCol = col + dc[i];40 41                if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n &&42                    grid[newRow][newCol] == 1 && !visited[newRow][newCol]) {43                    visited[newRow][newCol] = true;44                    queue.offer(new int[]{newRow, newCol});45                }46            }47        }48        return false; // No path to the boundary found49    }50}

Complexity

Time

O((m*n)²) - In the worst-case scenario, for each of the O(m*n) land cells, we might perform a traversal that visits all O(m*n) cells. This results in a quadratic time complexity.

Space

O(m*n) - For each check, a `visited` matrix of size m*n is created. The queue used for BFS can also grow up to O(m*n) in the worst case.

Trade-offs

Pros

Conceptually straightforward, as it directly translates the question: 'for each land cell, can it reach the boundary?'

Cons

Extremely inefficient due to massive redundant computations.
Traverses the same group of connected land cells multiple times, once for each cell in that group.
Likely to result in a 'Time Limit Exceeded' error on larger inputs.

This is a much more efficient approach. The core idea is that any land cell connected to a land cell on the boundary can also reach the boundary. Therefore, these cells are not part of an enclave. We can find all such cells by starting a traversal from the boundary land cells and 'sinking' or marking all connected land cells. The remaining, unmarked land cells are the ones that form enclaves.

Algorithm

Iterate over the cells on the four boundaries of the grid (top, bottom, left, right).
If a boundary cell is a land cell (1), start a traversal (DFS or BFS) from this cell.
The traversal finds all connected land cells. To mark these cells as 'visited' and 'connected to the boundary', we modify the grid in-place, changing their value from 1 to 0 (effectively 'sinking' them).
After the traversals from all boundary land cells are complete, the grid is modified such that only the true enclave cells remain as 1.
Finally, iterate through the entire modified grid and count the number of remaining 1s. This count is the final answer.

Walkthrough

Instead of checking from the inside out, we work from the outside in. We assume all land cells are enclaves, and then we disqualify any land cell that can touch the boundary. By starting our search from the boundary, we can find and mark all such 'non-enclave' cells in a single pass.

1class Solution {2    public int numEnclaves(int[][] grid) {3        int m = grid.length;4        int n = grid[0].length;5 6        // Start DFS from all '1's on the boundary to mark them and their connected components.7        for (int i = 0; i < m; i++) {8            // First column9            if (grid[i][0] == 1) {10                dfs(grid, i, 0);11            }12            // Last column13            if (grid[i][n - 1] == 1) {14                dfs(grid, i, n - 1);15            }16        }17 18        for (int j = 0; j < n; j++) {19            // First row20            if (grid[0][j] == 1) {21                dfs(grid, 0, j);22            }23            // Last row24            if (grid[m - 1][j] == 1) {25                dfs(grid, m - 1, j);26            }27        }28 29        // Count the remaining '1's, which are the enclaves.30        int count = 0;31        for (int i = 0; i < m; i++) {32            for (int j = 0; j < n; j++) {33                if (grid[i][j] == 1) {34                    count++;35                }36            }37        }38        return count;39    }40 41    private void dfs(int[][] grid, int r, int c) {42        int m = grid.length;43        int n = grid[0].length;44 45        if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] != 1) {46            return;47        }48 49        // Mark the cell as visited by 'sinking' it.50        grid[r][c] = 0;51 52        // Explore 4-directionally.53        dfs(grid, r + 1, c);54        dfs(grid, r - 1, c);55        dfs(grid, r, c + 1);56        dfs(grid, r, c - 1);57    }58}

Complexity

Time

O(m * n) - In the worst case, the traversal (DFS/BFS) visits every cell in the grid once. The initial boundary scan and the final count also take O(m*n) time, leading to a linear time complexity overall.

Space

O(m * n) - This is the worst-case space complexity for the recursion call stack in DFS. If the grid contains a long, winding path of land cells, the recursion depth can be proportional to the total number of cells. Using an iterative BFS would have the same worst-case space for its queue.

Trade-offs

Pros

Optimal time complexity of O(m*n).
Elegant and efficient logic by inverting the problem.
Avoids an explicit auxiliary visited matrix by modifying the input grid, which can be a space optimization.

Cons

Modifies the input grid, which might not be desirable in all scenarios. A copy would be needed if the original grid must be preserved, increasing space usage.
The recursion stack can still lead to a StackOverflowError on grids with very deep paths.

Solutions

Solution

1class Solution {2private3  int m;4private5  int n;6private7  int[][] grid;8public9  int numEnclaves(int[][] grid) {10    this.grid = grid;11    m = grid.length;12    n = grid[0].length;13    for (int i = 0; i < m; ++i) {14      for (int j = 0; j < n; ++j) {15        if (grid[i][j] == 1 && (i == 0 || i == m - 1 || j == 0 || j == n - 1)) {16          dfs(i, j);17        }18      }19    }20    int ans = 0;21    for (var row : grid) {22      for (var v : row) {23        ans += v;24      }25    }26    return ans;27  }28private29  void dfs(int i, int j) {30    grid[i][j] = 0;31    int[] dirs = {-1, 0, 1, 0, -1};32    for (int k = 0; k < 4; ++k) {33      int x = i + dirs[k], y = j + dirs[k + 1];34      if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1) {35        dfs(x, y);36      }37    }38  }39}

1class Solution {2public:3  int numEnclaves(vector<vector<int>> &grid) {4    int m = grid.size(), n = grid[0].size();5    int dirs[5] = {-1, 0, 1, 0, -1};6    function<void(int, int)> dfs = [&](int i, int j) {7      grid[i][j] = 0;8      for (int k = 0; k < 4; ++k) {9        int x = i + dirs[k], y = j + dirs[k + 1];10        if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y]) {11          dfs(x, y);12        }13      }14    };15    for (int i = 0; i < m; ++i) {16      for (int j = 0; j < n; ++j) {17        if (grid[i][j] && (i == 0 || i == m - 1 || j == 0 || j == n - 1)) {18          dfs(i, j);19        }20      }21    }22    int ans = 0;23    for (auto &row : grid) {24      for (auto &v : row) {25        ans += v;26      }27    }28    return ans;29  }30};

1class Solution:2    def numEnclaves(self, grid: List[List[int]]) -> int: def dfs(i, j): 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) m, n = len(grid), len(grid[0]) dirs = (- 1, 0, 1, 0, - 1) for i in range(m): for j in range(n): if grid[i][j] and (i == 0 or i == m - 1 or j == 0 or j == n - 1): dfs(i, j) return sum(v for row in grid for v in row)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem