Solution Explanation for Number of Enclaves

This problem asks to find the number of land cells (represented by 1s) in a binary matrix that are completely enclosed by sea cells (represented by 0s) and cannot be reached from the boundary of the matrix. We can solve this using Depth-First Search (DFS), Breadth-First Search (BFS), or Union-Find. Here's a detailed explanation of the DFS and BFS approaches, along with complexity analysis:

Approach 1: Depth-First Search (DFS)

This approach uses DFS to identify and mark all land cells connected to the boundary. Any remaining land cells are enclosed.

Algorithm:

1. Initialization: Iterate through the boundary of the grid. If a land cell is found, perform a DFS starting from that cell.

2. DFS: The DFS function recursively explores adjacent land cells, marking them as visited (changing their value to 0). It continues until it reaches a boundary or all connected land cells are visited.

3. Counting Enclaves: After the DFS, iterate through the grid again. The sum of the remaining 1s represents the number of enclosed land cells.

Code (Python):

def numEnclaves(grid):
    m, n = len(grid), len(grid[0])
    def dfs(i, j):
        if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] == 0:
            return
        grid[i][j] = 0  # Mark as visited
        dfs(i + 1, j)
        dfs(i - 1, j)
        dfs(i, j + 1)
        dfs(i, j - 1)
 
    for i in range(m):
        dfs(i, 0)  # Check left boundary
        dfs(i, n - 1)  # Check right boundary
    for j in range(n):
        dfs(0, j)  # Check top boundary
        dfs(m - 1, j)  # Check bottom boundary
 
    count = 0
    for i in range(m):
        for j in range(n):
            if grid[i][j] == 1:
                count += 1
    return count
 

Time Complexity: O(M*N), where M and N are the dimensions of the grid. We visit each cell at most once.

Space Complexity: O(M*N) in the worst case for the recursion stack during DFS (though it can be reduced to O(1) if an iterative approach with a stack is used instead).

Approach 2: Breadth-First Search (BFS)

This approach is similar to DFS, but uses a queue instead of recursion.

Algorithm:

1. Initialization: Find all land cells on the boundary and add them to a queue. Mark these cells as visited (change to 0).

2. BFS: While the queue is not empty, dequeue a cell and explore its adjacent cells. If an adjacent cell is a land cell, add it to the queue and mark it as visited.

3. Counting Enclaves: Similar to DFS, count the remaining 1s in the grid.

Code (Python):

from collections import deque
 
def numEnclaves(grid):
    m, n = len(grid), len(grid[0])
    q = deque()
    for i in range(m):
        if grid[i][0] == 1:
            q.append((i, 0))
            grid[i][0] = 0
        if grid[i][n - 1] == 1:
            q.append((i, n - 1))
            grid[i][n-1] = 0
    for j in range(n):
        if grid[0][j] == 1:
            q.append((0, j))
            grid[0][j] = 0
        if grid[m - 1][j] == 1:
            q.append((m - 1, j))
            grid[m - 1][j] = 0
 
    while q:
        i, j = q.popleft()
        for x, y in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
            if 0 <= x < m and 0 <= y < n and grid[x][y] == 1:
                q.append((x, y))
                grid[x][y] = 0
 
    count = sum(sum(row) for row in grid)
    return count
 

Time Complexity: O(M*N)

Space Complexity: O(M*N) in the worst case, for the queue.

Approach 3: Union-Find (Not shown in detail, but mentioned in the problem description)

Union-Find can also be used to solve this problem. It would involve creating a disjoint-set data structure to connect land cells. Cells connected to the boundary would be grouped into one set. The number of elements in other sets would represent the enclosed lands. This approach has similar time complexity to DFS and BFS.

Note: The provided code examples use different helper functions (pairwise in Python) or different ways to handle adjacent cells. The core logic of DFS or BFS remains the same across different programming languages.