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.
1#include <vector>
2using namespace std;
3
4void dfs(vector<vector<int>>& grid, int i, int j) {
5 if (i < 0 || j < 0 || i >= grid.size() || j >= grid[0].size() || grid[i][j] == 0) {
6 return;
7 }
8 grid[i][j] = 0;
9 dfs(grid, i + 1, j);
10 dfs(grid, i - 1, j);
11 dfs(grid, i, j + 1);
12 dfs(grid, i, j - 1);
13}
14
15int numEnclaves(vector<vector<int>>& grid) {
16 int m = grid.size();
17 int n = grid[0].size();
18
19 for (int i = 0; i < m; i++) {
20 if (grid[i][0] == 1) {
21 dfs(grid, i, 0);
22 }
23 if (grid[i][n-1] == 1) {
24 dfs(grid, i, n-1);
25 }
26 }
27 for (int j = 0; j < n; j++) {
28 if (grid[0][j] == 1) {
29 dfs(grid, 0, j);
30 }
31 if (grid[m-1][j] == 1) {
32 dfs(grid, m-1, j);
33 }
34 }
35
36 int count = 0;
37 for (int i = 0; i < m; i++) {
38 for (int j = 0; j < n; j++) {
39 if (grid[i][j] == 1) {
40 count++;
41 }
42 }
43 }
44 return count;
45}
46In C++, this solution follows the same logic as the C implementation. A depth-first search (DFS) is executed on grid cells, starting from the boundaries to mark all reachable land cells. Finally, it counts 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.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public int NumEnclaves(int[][] grid) {
6 int m = grid.Length;
7 int n = grid[0].Length;
8
9 void Bfs(int startRow, int startCol) {
10 Queue<(int, int)> queue = new Queue<(int, int)>();
11 queue.Enqueue((startRow, startCol));
12 grid[startRow][startCol] = 0;
13 int[][] directions = new int[][] { new int[] {1, 0}, new int[] {-1, 0}, new int[] {0, 1}, new int[] {0, -1} };
14 while (queue.Count > 0) {
15 var (r, c) = queue.Dequeue();
16 foreach (var dir in directions) {
17 int newRow = r + dir[0], newCol = c + dir[1];
18 if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && grid[newRow][newCol] == 1) {
19 grid[newRow][newCol] = 0;
20 queue.Enqueue((newRow, newCol));
21 }
22 }
23 }
24 }
25
26 for (int i = 0; i < m; i++) {
27 if (grid[i][0] == 1) Bfs(i, 0);
28 if (grid[i][n - 1] == 1) Bfs(i, n - 1);
29 }
30 for (int j = 0; j < n; j++) {
31 if (grid[0][j] == 1) Bfs(0, j);
32 if (grid[m - 1][j] == 1) Bfs(m - 1, j);
33 }
34
35 int count = 0;
36 for (int i = 0; i < m; i++) {
37 for (int j = 0; j < n; j++) {
38 if (grid[i][j] == 1) count++;
39 }
40 }
41 return count;
42 }
43}
44This C# solution makes use of a queue for BFS. Starting from boundary land cells, connected lands are explored and marked as zero. Unmarked remaining '1's are counted as enclave cells.