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.
1public class Solution {
2 public int NumEnclaves(int[][] grid) {
3 int m = grid.Length;
4 int n = grid[0].Length;
5
6 void Dfs(int i, int j) {
7 if (i < 0 || j < 0 || i >= m || j >= n || grid[i][j] == 0) {
8 return;
9 }
10 grid[i][j] = 0;
11 Dfs(i + 1, j);
12 Dfs(i - 1, j);
13 Dfs(i, j + 1);
14 Dfs(i, j - 1);
15 }
16
17 for (int i = 0; i < m; i++) {
18 if (grid[i][0] == 1) {
19 Dfs(i, 0);
20 }
21 if (grid[i][n - 1] == 1) {
22 Dfs(i, n - 1);
23 }
24 }
25 for (int j = 0; j < n; j++) {
26 if (grid[0][j] == 1) {
27 Dfs(0, j);
28 }
29 if (grid[m - 1][j] == 1) {
30 Dfs(m - 1, j);
31 }
32 }
33
34 int count = 0;
35 for (int i = 0; i < m; i++) {
36 for (int j = 0; j < n; j++) {
37 if (grid[i][j] == 1) {
38 count++;
39 }
40 }
41 }
42 return count;
43 }
44}
45This C# code implements similar logic: iterating over boundary cells and using DFS to mark reachable land cells. Enclaves are counted by checking the remaining unmarked land cells.
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.
1#include <stdio.h>
2#include <stdlib.h>
3
4typedef struct {
5 int row;
6 int col;
7} Point;
8
9int** directions = (int* []){(int[]){1, 0}, (int[]){-1, 0}, (int[]){0, 1}, (int[]){0, -1}};
10
11void bfs(int** grid, int m, int n, int startRow, int startCol) {
12 Point* queue = (Point*)malloc(m * n * sizeof(Point));
13 int front = 0, rear = 0;
14 queue[rear++] = (Point){startRow, startCol};
15 grid[startRow][startCol] = 0;
16 while (front < rear) {
17 Point current = queue[front++];
18 for (int d = 0; d < 4; d++) {
19 int newRow = current.row + directions[d][0];
20 int newCol = current.col + directions[d][1];
21 if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && grid[newRow][newCol] == 1) {
22 grid[newRow][newCol] = 0;
23 queue[rear++] = (Point){newRow, newCol};
24 }
25 }
26 }
27 free(queue);
28}
29
30int numEnclaves(int** grid, int gridSize, int* gridColSize) {
31 int m = gridSize, n = *gridColSize;
32
33 for (int i = 0; i < m; i++) {
34 if (grid[i][0] == 1) bfs(grid, m, n, i, 0);
35 if (grid[i][n - 1] == 1) bfs(grid, m, n, i, n - 1);
36 }
37 for (int j = 0; j < n; j++) {
38 if (grid[0][j] == 1) bfs(grid, m, n, 0, j);
39 if (grid[m - 1][j] == 1) bfs(grid, m, n, m - 1, j);
40 }
41
42 int count = 0;
43 for (int i = 0; i < m; i++) {
44 for (int j = 0; j < n; j++) {
45 if (grid[i][j] == 1) count++;
46 }
47 }
48 return count;
49}
50This C implementation uses a BFS method where we use a queue to explore all land cells connected to the boundary. As the boundary is iterated, each connected land cell is marked by setting its value to zero (i.e., visited).