Leetcode 1020. Number of Enclaves

Problem Explanation:

We are given a 2D array representing a map, where '0' represents the sea and '1' represents the land. A move is allowed from any land square to any neighbouring land square or off the boundary of the grid. Movements are possible in all four directions. The goal of the problem is to find the number of land squares from which it is not possible to exit the grid or reach the boundary.

For instance, if we are given a 2D array [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]], we are able to walk off the boundary from all '1's except three, so the output should be 3.

Approach:

The idea behind the solution is to use Depth-first search to check all border lands and all lands that are connected to them, and mark them as '0'. Finally, we simply need to calculate the remaining '1's (land squares) in the grid, which will be the land squares from which we cannot walk off the boundary of the grid.

Step by step solution:

1. Iterate each cell in the matrix, if the cell is '1' and it's on the edge of the matrix, we start a Depth-First Search from this cell.

2. In the DFS, we first check if the current cell is within the boundary. If it's out of boundary we return from the current call.

3. If the current cell is a '0' or already visited then we return from the current call. If it's a '1', we mark it as visited by setting its value as '0' and call the DFS for its four neighbouring cells.

4. Now, we have marked all cells which are connected to the boundary cells directly or indirectly via other '1's. The remaining '1's in the grid are the cells which are not connected to the boundary '1's. Hence, they are the answer to this problem.

Example:

Let's walk through an example `[[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]

After applying DFS for '1's on the boundary, we get [[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]]

The land squares from which we cannot walk off the boundary of the grid in this case is 0, which is the remaining '1's in the grid.

Python Solution:

1
2python
3class Solution:
4    def numEnclaves(self, A):
5        if not A or not A[0]: return 0
6        
7        m, n = len(A), len(A[0])
8        
9        def dfs(i, j):
10            A[i][j] = 0
11            for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
12                nx, ny = i + dx, j + dy
13                if 0 <= nx < m and 0 <= ny < n and A[nx][ny] == 1:
14                    dfs(nx, ny)
15        
16        for i in range(m):
17            if A[i][0] == 1: dfs(i, 0)
18            if A[i][n - 1] == 1: dfs(i, n - 1)
19        for j in range(n):
20            if A[0][j] == 1: dfs(0, j)
21            if A[m - 1][j] == 1: dfs(m - 1, j)
22        
23        return sum([sum(row) for row in A])

In the above solution, we first perform dfs for any '1's on the boundary of the grid. As part of dfs, if we encounter any '1' cell, we make it '0' and perform dfs on the four neighboring cells. After performing dfs for all edge '1's, we return the count of remaining '1's in the grid.JavaScript Solution:

1
2javascript
3var numEnclaves = function(A) {
4    function dfs(i, j) {
5        if(i<0 || i>=A.length || j<0 || j>=A[0].length || A[i][j] === 0) return;
6        A[i][j] = 0;
7        dfs(i-1,j);
8        dfs(i+1,j);
9        dfs(i,j-1);
10        dfs(i,j+1);
11    }
12    
13    for(let i=0; i<A.length; i++) {
14        for(let j=0; j<A[0].length; j++) {
15            if(i===0 || i===A.length-1 || j===0 || j===A[0].length-1) {
16                dfs(i, j);
17            }
18        }
19    }
20    
21    let count = 0;
22    for(let i=0; i<A.length; i++) {
23        for(let j=0; j<A[0].length; j++) {
24            if(A[i][j] === 1) count++;
25        }
26    }
27    return count;
28};

In the JavaScript solution, We first perform Depth-first search for any '1's on the boundary of the grid. As part of DFS, if we encounter any '1' cell, we make it '0' and perform DFS on the four neighboring cells. After performing DFS for all edge '1's, we return the count of remaining '1's in the grid.

Java Solution:

1
2java
3class Solution {
4    private int[][] A;
5    private int rows, cols;
6    
7    public int numEnclaves(int[][] A) {
8        this.A = A;
9        this.rows = A.length;
10        this.cols = A[0].length;
11        for (int i = 0; i < rows; i++) {
12            dfs(i, 0);
13            dfs(i, cols - 1);
14        }
15        for (int j = 0; j < cols; j++) {
16            dfs(0, j);
17            dfs(rows - 1, j);
18        }
19        int count = 0;
20        for (int i = 0; i < rows; i++) {
21            for (int j = 0; j < cols; j++) {
22                count += A[i][j];
23            }
24        }
25        return count;
26    }
27
28    private void dfs(int i, int j) {
29        if (i < 0 || i >= rows || j < 0 || j >= cols || A[i][j] == 0)
30            return;
31        A[i][j] = 0;
32        dfs(i + 1, j);
33        dfs(i - 1, j);
34        dfs(i, j + 1);
35        dfs(i, j - 1);
36    }
37}

In the Java solution, We first perform Depth-first search for any '1's on the boundary of the grid. As a part of DFS, if we encounter any '1' cell, we make it '0' and perform DFS on the four neighboring cells. After performing DFS for all edge '1's, we return the count of remaining '1's in the grid.