Solution For Number Of Enclaves

Problem Statement:

Given a 2D array A, containing only 0’s and 1’s, find the number of “enclaves”. An enclave is a region of connected 1’s in the matrix that is not connected to the border of the matrix.

Solution:

To solve the Number of Enclaves problem, we need to first identify all the connected components of 1’s in the given matrix.

We can do this using a recursive DFS approach, where we start from each cell containing a 1, and recursively explore all its neighboring cells which contain a 1. We mark each explored cell as visited to avoid visiting it again.

After we have identified all the connected components of 1’s, we can check if each of them is connected to the border of the matrix or not.

If a connected component is not connected to the border, then it is an enclave and we increment the count of enclaves.

To check if a connected component is connected to the border, we can start from all cells on the border of the matrix, and perform a DFS to check if any of these cells are connected to the connected component.

Code:

Here is the Python code to solve the Number of Enclaves problem:

“`
class Solution:
def numEnclaves(self, A: List[List[int]]) -> int:
m, n = len(A), len(A[0])
visited = set()

    def dfs(i, j):
        if i < 0 or i >= m or j < 0 or j >= n or A[i][j] == 0 or (i, j) in visited:
            return
        visited.add((i, j))
        dfs(i+1, j)
        dfs(i-1, j)
        dfs(i, j+1)
        dfs(i, j-1)

    # Find all connected components of 1's
    for i in range(m):
        for j in range(n):
            if A[i][j] == 1 and (i, j) not in visited:
                dfs(i, j)

    # Check if each connected component is an enclave
    enclaves = 0
    for i in range(m):
        for j in range(n):
            if A[i][j] == 1 and (i, j) not in visited:
                connected_to_border = False
                border_cells = [(i, j)]
                visited.add((i, j))
                while border_cells:
                    x, y = border_cells.pop()
                    if x == 0 or x == m-1 or y == 0 or y == n-1:
                        connected_to_border = True
                    for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                        nx, ny = x+dx, y+dy
                        if nx >= 0 and nx < m and ny >= 0 and ny < n and A[nx][ny] == 1 and (nx, ny) not in visited:
                            visited.add((nx, ny))
                            border_cells.append((nx, ny))
                if not connected_to_border:
                    enclaves += 1

    return enclaves

“`

Time Complexity:

The time complexity of the above solution is O(mn), where m is the number of rows and n is the number of columns in the matrix. We visit each cell at most once during the DFS.

Step by Step Implementation For Number Of Enclaves

class Solution {
    public int numEnclaves(int[][] A) {
        int rows = A.length;
        int cols = A[0].length;
        int result = 0;
        
        for(int i = 0; i < rows; i++){
            for(int j = 0; j < cols; j++){
                if(A[i][j] == 1){
                    result++;
                }
                A[i][j] = 0;
            }
        }
        
        return result;
    }
}

class Solution:
    def numEnclaves(self, A: List[List[int]]) -> int:
        # keep track of visited nodes
        visited = set()
        
        # do a DFS from each 0 node
        for i in range(len(A)):
            for j in range(len(A[0])):
                # if we find a 0 node, do a DFS
                if A[i][j] == 0 and (i, j) not in visited:
                    # keep track of nodes in this DFS
                    curr_set = set()
                    # do a DFS starting from (i, j)
                    self.DFS(A, i, j, visited, curr_set)
                    # if this DFS found any 1 nodes, it's not an enclave
                    if 1 in curr_set:
                        visited = visited.union(curr_set)
        
        # count the number of unvisited 1 nodes
        count = 0
        for i in range(len(A)):
            for j in range(len(A[0])):
                if A[i][j] == 1 and (i, j) not in visited:
                    count += 1
        
        return count
                    
    def DFS(self, A, i, j, visited, curr_set):
        # mark (i, j) as visited
        visited.add((i, j))
        # add (i, j) to the current set
        curr_set.add(A[i][j])
        
        # explore neighbors
        for x, y in [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]:
            # if the neighbor is valid and unvisited, explore it
            if 0 <= x < len(A) and 0 <= y < len(A[0]) and (x, y) not in visited:
                self.DFS(A, x, y, visited, curr_set)

var numEnclaves = function(A) {
    let count = 0;
    for(let i=0; i=A.length || j<0 || j>=A[0].length || A[i][j] != 1) {
        return;
    }
    
    A[i][j] = 0;
    
    dfs(A, i+1, j);
    dfs(A, i-1, j);
    dfs(A, i, j+1);
    dfs(A, i, j-1);
}

There are several ways to solve this problem. One approach would be to use a flood fill algorithm, starting from the '0' cells and marking all connected '1' cells as visited. Then, we can simply count the number of unvisited '1' cells, which will be the number of enclaves.

Another approach would be to keep track of the number of '1' cells reachable from each '0' cell, using a breadth-first search. Then, we can iterate over all '1' cells and check whether there is a '0' cell reachable from it. The number of '1' cells for which this is not the case will be the number of enclaves.

public int NumEnclaves(int[][] A) { //BFS solution //Create a visited array to keep track of visited nodes bool[][] visited = new bool[A.Length][A[0].Length]; int result = 0; //Loop through each cell in the array for (int i = 0; i < A.Length; i++) { for (int j = 0; j < A[0].Length; j++) { //If the cell is an island and has not been visited yet if (A[i][j] == 1 && !visited[i][j]) { //Perform a BFS to find the size of the island int size = BFS(A, i, j, visited); //Add the size of the island to the result result += size; } } } return result; } public int BFS(int[][] A, int i, int j, bool[][] visited) { //Create a queue to store nodes to visit Queue queue = new Queue(); //Add the starting node to the queue and mark it as visited queue.Enqueue(new int[] { i, j }); visited[i][j] = true; int size = 0; //Loop through the queue while (queue.Count != 0) { //Get the next node int[] node = queue.Dequeue(); size++; //Get the row and column of the node int row = node[0]; int col = node[1]; //Check all the adjacent nodes for (int r = row - 1; r <= row + 1; r++) { for (int c = col - 1; c <= col + 1; c++) { //Make sure the adjacent node is valid (i.e. not out of bounds, not visited, and is an island) if (r >= 0 && r < A.Length && c >= 0 && c < A[0].Length && A[r][c] == 1 && !visited[r][c]) { //Add the node to the queue and mark it as visited queue.Enqueue(new int[] { r, c }); visited[r][c] = true; } } } } //Return the size of the island return size; }