See all coding puzzles and patterns here.

Problem Definition

Given a matrix grid where $0$ represents a sea cell and $1$ represents a land cell, find the number of land cells that can't be reached via traversal from the edges of the grid if only compass moves (up, down, left, right) are allowed (diagonal moves are not allowed).

Examples

Some test cases to verify our solution. 

assert number_of_enclaves([
    [0, 0, 0, 0],
    [1, 0, 1, 0],
    [0, 1, 1, 0],
    [0, 0, 0, 0]
]) == 3

assert number_of_enclaves([
    [0, 0, 1, 0],
    [1, 0, 1, 0],
    [0, 1, 1, 0],
    [0, 0, 0, 0]
]) == 0

Solution

This is a graph traversal problem that we can solve with either a depth-first traversal or breadth-first traversal. Here, we implement a DFS solution.

We want to start from the edges and traverse all land cells connected to the edges, making them as visited along the way. We then loop over all cells and count the number of land cells that were not visited. 

def get_directions(row, col, r_max, c_max):
    directions = []
    if row - 1 >= 0:
        directions.append((row - 1, col))
    if row + 1 < r_max:
        directions.append((row + 1, col))
    if col - 1 >= 0:
        directions.append((row, col - 1))
    if col + 1 < c_max:
        directions.append((row, col + 1))
    return directions

def number_of_enclaves(grid: list[list[int]]) -> int:
    visited = set()
    r_max = len(grid)
    c_max = len(grid[0])

    def dfs(r, c):
        stack = [(r, c)]
        while stack:
            row, col = stack.pop()
            visited.add((row, col))
            for r, c in get_directions(row, col, r_max, c_max):
                if grid[r][c] and (r, c) not in visited:
                    stack.append((r, c))

    for row in (0, r_max - 1):
        for col in range(c_max):
            if grid[row][col] and (row, col) not in visited:
                dfs(row, col)
    for col in (0, c_max - 1):
        for row in range(r_max):
            if grid[row][col] and (row, col) not in visited:
                dfs(row, col)

    count = 0
    for row in range(r_max):
        for col in range(c_max):
            if grid[row][col] and (row, col) not in visited:
                count += 1
    return count

Complexity

Let $n = $ the number of nodes in the grid.

Runtime complexity should be $\Theta(n)$ since we are visiting every node once.

Auxiliary space complexity should also be $\Theta(n)$ since visited will grow to size $n$.