#1020

Medium

auto_awesomeArray plus Depth-First Search

LeetCode Problem Workspace

Number of Enclaves

This problem involves finding the number of land cells that cannot reach the boundary in a grid using DFS and array manipulation.

array depth first search breadth first search union find matrix

Problem Statement

You are given a binary matrix of size m x n, where each cell is either a sea (0) or land (1). Your task is to count the number of land cells that cannot reach any boundary, meaning they are fully enclosed by sea cells.

A valid move consists of walking to an adjacent land cell (either horizontally or vertically) or moving off the grid's boundary. Boundary land cells, or those connected to them, are not enclosed. You need to return the number of land cells that remain fully enclosed by sea cells and can't reach the boundary.

Examples

Example 1

Input: grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]

Output: 3

There are three 1s that are enclosed by 0s, and one 1 that is not enclosed because its on the boundary.

Example 2

Input: grid = [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]

Output: 0

All 1s are either on the boundary or can reach the boundary.

Constraints

m == grid.length
n == grid[i].length
1 <= m, n <= 500
grid[i][j] is either 0 or 1.

Solution Approach

DFS from Boundary Cells

The solution begins by marking all land cells connected to the boundary. Start DFS from each boundary land cell, marking all reachable cells as non-enclosed. Then, simply count the land cells that remain unmarked, which are the fully enclosed ones.

Iterate Through Boundary

Instead of recursively checking the grid, you can first iterate through the boundary and run DFS on any land cell found. This step ensures that all connected land cells are correctly marked as not enclosed, simplifying the counting process.

Graph Representation of the Grid

Model the grid as a graph, where each land cell is a node. The edges connect adjacent land cells, and the boundary cells form the outer layer. By performing DFS or BFS from boundary nodes, we can efficiently determine which land cells are enclosed by water.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the DFS traversal, which visits each cell once, resulting in O(m * n) time. The space complexity also depends on the recursion stack used for DFS, which can go as deep as O(m * n) in the worst case.

What Interviewers Usually Probe

Candidate understands how to traverse the grid with DFS.
Candidate correctly identifies boundary-connected land cells.
Candidate shows ability to adapt grid problems to graph-based thinking.

Common Pitfalls or Variants

Common pitfalls

Forgetting to mark boundary-connected cells, which can lead to incorrect counting of enclosed cells.
Not handling edge cases such as very small grids or all sea cells.
Confusing DFS/BFS traversal direction, leading to missed cells.

Follow-up variants

Adjusting the problem to check for different kinds of enclosed regions (e.g., with obstacles).
Handling 3D grid problems where cells can be connected in more than two dimensions.
Using BFS instead of DFS for exploring grid connections.

FAQ

How can I use DFS to solve the Number of Enclaves problem?

You can start by marking all land cells connected to the boundary. Then, use DFS to explore and mark all reachable land cells as non-enclosed.

What is the primary challenge in solving the Number of Enclaves?

The main challenge is ensuring that boundary-connected land cells are correctly marked so that only truly enclosed land cells are counted.

Can I solve the Number of Enclaves problem without DFS?

Yes, you can use BFS as an alternative to DFS to explore the grid and mark boundary-connected land cells.

What is the time complexity of solving this problem?

The time complexity is O(m * n), where m and n are the dimensions of the grid. This is because DFS or BFS will visit every cell once.

How does GhostInterview assist with this problem?

GhostInterview helps by guiding you through the DFS or BFS traversal and providing tips on grid traversal strategies for similar problems.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

class Solution:
    def numEnclaves(self, grid: List[List[int]]) -> int:
        def dfs(i: int, j: int):
            grid[i][j] = 0
            for a, b in pairwise(dirs):
                x, y = i + a, j + b
                if 0 <= x < m and 0 <= y < n and grid[x][y]:
                    dfs(x, y)

        m, n = len(grid), len(grid[0])
        dirs = (-1, 0, 1, 0, -1)
        for j in range(n):
            if grid[0][j]:
                dfs(0, j)
            if grid[m - 1][j]:
                dfs(m - 1, j)
        for i in range(m):
            if grid[i][0]:
                dfs(i, 0)
            if grid[i][n - 1]:
                dfs(i, n - 1)
        return sum(sum(row) for row in grid)

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

class Solution:
    def numEnclaves(self, grid: List[List[int]]) -> int:
        def dfs(i: int, j: int):
            grid[i][j] = 0
            for a, b in pairwise(dirs):
                x, y = i + a, j + b
                if 0 <= x < m and 0 <= y < n and grid[x][y]:
                    dfs(x, y)

        m, n = len(grid), len(grid[0])
        dirs = (-1, 0, 1, 0, -1)
        for j in range(n):
            if grid[0][j]:
                dfs(0, j)
            if grid[m - 1][j]:
                dfs(m - 1, j)
        for i in range(m):
            if grid[i][0]:
                dfs(i, 0)
            if grid[i][n - 1]:
                dfs(i, n - 1)
        return sum(sum(row) for row in grid)

Solution 3

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

class Solution:
    def numEnclaves(self, grid: List[List[int]]) -> int:
        def dfs(i: int, j: int):
            grid[i][j] = 0
            for a, b in pairwise(dirs):
                x, y = i + a, j + b
                if 0 <= x < m and 0 <= y < n and grid[x][y]:
                    dfs(x, y)

        m, n = len(grid), len(grid[0])
        dirs = (-1, 0, 1, 0, -1)
        for j in range(n):
            if grid[0][j]:
                dfs(0, j)
            if grid[m - 1][j]:
                dfs(m - 1, j)
        for i in range(m):
            if grid[i][0]:
                dfs(i, 0)
            if grid[i][n - 1]:
                dfs(i, n - 1)
        return sum(sum(row) for row in grid)

Continue Practicing

#959 regions cut by slashes #827 making a large island #1254 number of closed islands