Number of Enclaves - Solution & Explanation
Problem Statement
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 either0or1.
Approach Overview
Problem Overview: You are given a binary grid where 1 represents land and 0 represents water. An enclave is a land cell that cannot walk off the grid boundary by moving up, down, left, or right. The task is to count how many land cells are completely surrounded by water and cannot reach any boundary cell.
Approach 1: Depth-First Search (DFS) Flood Fill (Time: O(m*n), Space: O(m*n))
The key observation: land connected to the grid boundary can never be an enclave. Instead of searching for enclosed regions directly, eliminate all boundary-connected land first. Iterate over the grid edges and start a Depth-First Search from every boundary land cell. During DFS, mark each reachable land cell as water (or visited). This effectively removes every land region that can escape the grid. After the flood fill completes, iterate through the grid again and count the remaining 1 cells. Those are enclaves because they were never connected to the border.
This approach works because each cell is visited at most once during DFS traversal. The grid itself acts as the visited structure by flipping land to water. DFS is straightforward to implement and works well when recursion depth is manageable.
Approach 2: Breadth-First Search (BFS) Flood Fill (Time: O(m*n), Space: O(m*n))
This approach follows the same boundary-elimination idea but uses a queue-based Breadth-First Search. First scan the border of the matrix and push every boundary land cell into a queue. Then repeatedly pop cells and explore their four neighbors. If a neighbor is land, mark it visited and push it into the queue. BFS spreads outward from the edges and removes every land cell connected to the boundary.
After the BFS traversal finishes, any remaining land cells must be enclosed regions. A final pass over the grid counts them. BFS avoids recursion depth issues and is often preferred in languages where deep recursion can cause stack overflow.
Recommended for interviews: The boundary flood-fill idea is the expected insight. Either DFS or BFS works with identical O(m*n) time complexity because every cell is processed at most once. DFS is slightly shorter to code, while BFS is safer when recursion depth could exceed limits. Interviewers mainly look for the realization that you should start from boundary land and remove reachable cells instead of trying to detect enclaves directly.
Approach 1: Approach 1: Depth-First Search (DFS)
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.
Complexity
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.
Approach 2: Approach 2: Breadth-First Search (BFS)
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).
Complexity
Time Complexity: O(m * n).
Space Complexity: O(min(m, n)) considering the queue size in the worst case.
Approach 3: Default Approach
Try this approach in the editor →Complexity Comparison
| 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). |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Depth-First Search (DFS) Flood Fill | O(m*n) | O(m*n) recursion stack worst case | Simple implementation when recursion depth is manageable |
| Breadth-First Search (BFS) Flood Fill | O(m*n) | O(m*n) queue in worst case | Preferred when avoiding recursion or stack overflow concerns |
Video Solution
G-15. Number of Enclaves | Multi-source BFS | C++ | Java • take U forward • 254,824 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Number of Enclaves easy or hard?
How to solve Number of Enclaves in O(n)?
What is the best approach for Number of Enclaves?
Is Number of Enclaves asked at Google/Amazon/Meta?
What data structure is used in Number of Enclaves?
What is the time complexity of Number of Enclaves?
Number of Enclaves Python or Java solution approach?
Ready to solve this problem?
Practice Number of Enclaves with our built-in code editor and test cases.
Practice on FleetCode