You are given an m x n binary matrix grid, where 0 represents a sea cell and 1 represents a land cell.
A move consists of walking from one land cell to another adjacent (4-directionally) land cell or walking off the boundary of the grid.
Return the number of land cells in grid for which we cannot walk off the boundary of the grid in any number of moves.
Example 1:
Input: grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]] Output: 3 Explanation: 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 Explanation: All 1s are either on the boundary or can reach the boundary.
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 500grid[i][j] is either 0 or 1.This approach uses a depth-first search (DFS) to mark land cells connected to the boundaries. We iterate over the boundary cells of the grid and if a land cell is found, we perform DFS to mark all connected land cells as visited. Finally, we count all remaining unvisited land cells inside the grid, which are considered enclaves.
This C code defines a function dfs that marks land cells ('1') as water ('0'), effectively marking them as visited. The main function numEnclaves iterates over the borders of the grid. For each unvisited land cell on the border, DFS is called to mark connected land. Finally, it counts all unvisited land cells inside the grid as enclaves.
C++
Java
Python
C#
JavaScript
Time Complexity: O(m * n) as each cell is visited at most once.
Space Complexity: O(m * n) in the worst case due to recursion stack used by DFS.
In this approach, we use a queue to perform BFS to mark land cells connected to the boundaries. By enqueueing each boundary land cell and exploring its neighbors iteratively, we can mark all reachable boundary-connected lands. This is followed by counting the unvisited land cells – those are the enclaves.
This C implementation uses a BFS method where we use a queue to explore all land cells connected to the boundary. As the boundary is iterated, each connected land cell is marked by setting its value to zero (i.e., visited).
C++
Java
Python
C#
JavaScript
Time Complexity: O(m * n).
Space Complexity: O(min(m, n)) considering the queue size in the worst case.
| Approach | Complexity |
|---|---|
| Approach 1: Depth-First Search (DFS) | Time Complexity: O(m * n) as each cell is visited at most once. |
| Approach 2: Breadth-First Search (BFS) | Time Complexity: O(m * n). |
G-15. Number of Enclaves | Multi-source BFS | C++ | Java • take U forward • 167,445 views views
Watch 9 more video solutions →Practice Number of Enclaves with our built-in code editor and test cases.
Practice on FleetCode