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.The goal of #1020 Number of Enclaves is to count the number of land cells in a grid that cannot reach the boundary by moving in four directions. A key insight is that any land cell connected to the boundary cannot be part of an enclave.
A common strategy is to start from the boundary cells and eliminate all land connected to the edges using Depth-First Search (DFS) or Breadth-First Search (BFS). By traversing from boundary land cells and marking them as visited or converting them to water, we effectively remove all non-enclave land. After this traversal, the remaining land cells in the grid represent enclaves.
An alternative approach uses Union Find (Disjoint Set) to group connected land cells and track whether a group touches the boundary. Only groups not connected to the border are counted.
Both traversal approaches process each cell at most once, resulting in efficient performance for typical matrix sizes.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| DFS / BFS from Boundary | O(m × n) | O(m × n) in worst case due to recursion/queue |
| Union Find | O(m × n · α(m × n)) | O(m × n) |
take U forward
Use these hints if you're stuck. Try solving on your own first.
Can you model this problem as a graph problem? Create n * m + 1 nodes where n * m nodes represents each cell of the map and one extra node to represent the exterior of the map.
In the map add edges between neighbors on land cells. And add edges between the exterior and land nodes which are in the boundary. Return as answer the number of nodes that are not reachable from the exterior node.
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.
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.
1#include <stdio.h>
2
3void dfs(int** grid, int m, int n, int i, int j) {
4 if
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.
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.
Time Complexity: O(m * n).
Space Complexity: O(min(m, n)) considering the queue size in the worst case.
1#
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, grid traversal problems like Number of Enclaves are common in FAANG-style interviews. They test understanding of DFS, BFS, graph connectivity, and matrix traversal techniques.
The optimal approach is to start DFS or BFS from all boundary land cells and mark every reachable land cell. After removing these cells, the remaining land cells in the grid are enclaves. This method ensures each cell is processed at most once.
Graph traversal structures like recursion stacks for DFS or queues for BFS work best. These help explore all connected land cells efficiently in the grid. Union Find can also be used to track connected components and detect boundary connections.
Any land connected to the boundary can eventually reach the grid edge, so it cannot be an enclave. By marking all land reachable from the boundary first, we isolate only the cells fully surrounded by water.
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).