Number Of Enclaves - Leetcode Solution

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.

1