In this problem, you're tasked with finding the number of land cells that are fully enclosed within the grid and cannot reach the boundary. This is achieved by marking all boundary-connected land cells and then counting the remaining enclosed cells. Depth-First Search (DFS) is typically used for exploring all connected land cells starting from the boundaries to mark accessible cells.
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.
How GhostInterview Helps
- Provides insights on handling connected components in grid-based problems using DFS.
- Assists in visualizing the grid as a graph, facilitating easier traversal decisions.
- Offers step-by-step guidance on efficiently solving grid problems using DFS or BFS.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
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.
Need direct help with Number of Enclaves instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Number of Enclaves from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Determine the number of regions in a grid divided by slashes using array scanning and union-find techniques efficiently.
Open problem page#827 Making A Large IslandCalculate the largest island size by converting at most one zero in a binary grid using array and DFS techniques efficiently.
Open problem page#1254 Number of Closed IslandsCount the number of closed islands in a 2D grid using array traversal and depth-first search efficiently.
Open problem page