This approach uses a depth-first search (DFS) to mark land cells connected to the boundaries. We iterate over the boundary cells of the grid and if a land cell is found, we perform DFS to mark all connected land cells as visited. Finally, we count all remaining unvisited land cells inside the grid, which are considered enclaves.
Time Complexity: O(m * n) as each cell is visited at most once.
Space Complexity: O(m * n) in the worst case due to recursion stack used by DFS.
1class Solution {
2 public int numEnclaves(int[][] grid) {
3 int m = grid.length, n = grid[0].length;
4 for (int i = 0; i < m; i++) {
5 if (grid[i][0] == 1) {
6 dfs(grid, i, 0);
7 }
8 if (grid[i][n - 1] == 1) {
9 dfs(grid, i, n - 1);
10 }
11 }
12 for (int j = 0; j < n; j++) {
13 if (grid[0][j] == 1) {
14 dfs(grid, 0, j);
15 }
16 if (grid[m - 1][j] == 1) {
17 dfs(grid, m - 1, j);
18 }
19 }
20
21 int count = 0;
22 for (int i = 0; i < m; i++) {
23 for (int j = 0; j < n; j++) {
24 if (grid[i][j] == 1) {
25 count++;
26 }
27 }
28 }
29 return count;
30 }
31
32 private void dfs(int[][] grid, int i, int j) {
33 if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == 0) {
34 return;
35 }
36 grid[i][j] = 0;
37 dfs(grid, i + 1, j);
38 dfs(grid, i - 1, j);
39 dfs(grid, i, j + 1);
40 dfs(grid, i, j - 1);
41 }
42}
43This Java solution defines a DFS helper method to explore connected land cells from the borders. All such land cells are marked, and finally, the remaining land cells are counted as enclaves.
In this approach, we use a queue to perform BFS to mark land cells connected to the boundaries. By enqueueing each boundary land cell and exploring its neighbors iteratively, we can mark all reachable boundary-connected lands. This is followed by counting the unvisited land cells – those are the enclaves.
Time Complexity: O(m * n).
Space Complexity: O(min(m, n)) considering the queue size in the worst case.
1import java.util.LinkedList;
2import java.util.Queue;
3
4class Solution {
5 public int numEnclaves(int[][] grid) {
6 int m = grid.length, n = grid[0].length;
7
8 for (int i = 0; i < m; i++) {
9 if (grid[i][0] == 1) bfs(grid, i, 0);
10 if (grid[i][n - 1] == 1) bfs(grid, i, n - 1);
11 }
12 for (int j = 0; j < n; j++) {
13 if (grid[0][j] == 1) bfs(grid, 0, j);
14 if (grid[m - 1][j] == 1) bfs(grid, m - 1, j);
15 }
16
17 int count = 0;
18 for (int i = 0; i < m; i++) {
19 for (int j = 0; j < n; j++) {
20 if (grid[i][j] == 1) count++;
21 }
22 }
23 return count;
24 }
25
26 private void bfs(int[][] grid, int i, int j) {
27 int m = grid.length, n = grid[0].length;
28 Queue<int[]> q = new LinkedList<>();
29 q.offer(new int[]{i, j});
30 grid[i][j] = 0;
31 int[][] directions =new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
32 while (!q.isEmpty()) {
33 int[] cell = q.poll();
34 for (int[] dir : directions) {
35 int newRow = cell[0] + dir[0];
36 int newCol = cell[1] + dir[1];
37 if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && grid[newRow][newCol] == 1) {
38 grid[newRow][newCol] = 0;
39 q.offer(new int[]{newRow, newCol});
40 }
41 }
42 }
43 }
44}
45In this Java solution, BFS uses a queue to propagate from land cells on boundaries. The queue expands connected land cells, marking them as visited. Remaining uncounted land cells are returned as result.