Problem Breakdown
We are given an m x n binary matrix representing land (1) and sea (0). The goal is to count how many land cells are “trapped” or enclaved—meaning they cannot reach any boundary of the grid by moving only through adjacent land cells. If a path exists from a specific land cell to the edge (walking off), that cell does not contribute to our final count.
Inputs:
grid: A 2D list of integers (0or1).- Dimensions:
m x n.
Outputs:
- An integer representing the count of trapped land cells.
Implicit Constraints & Edge Cases:
- Empty Grid: The constraints state dimensions are at least 1, so we don’t need to handle empty lists explicitly, but good code handles them gracefully (returning 0).
- All Land / All Sea: If the grid is all
1s and touches boundaries, count should be 0. If it’s a single cell on boundary, count is 0; if surrounded by sea in a larger grid, logic holds. - Stack Depth: Since this involves traversal (DFS/BFS), we must consider recursion limits for very deep paths of
1s (though LeetCode environments usually handle standard DFS depth).
Intuition
A naive approach would be to iterate through every land cell and run a search (BFS/DFS) from that specific cell to see if it can reach the boundary.
- Brute Force Complexity: For each of
m * ncells, we might traverse up toO(m + n)steps in worst case per component check? Actually, checking connectivity for every node individually leads to O((MN)^2) or at least O(MN*(M+N)) depending on implementation. This is too slow given constraints (500x500).
Key Insight:
Connectivity is transitive and symmetric. If a land cell can reach the boundary, it belongs to a connected component that touches an edge. Instead of checking every 1 individually against the edges, we should start our traversal from all known “escape routes”—the land cells located on the grid’s perimeter (first row, last row, first column, last column).
By performing a flood-fill (DFS/BFS) starting only from these boundary-connected components and marking them as visited/escaped, any 1 that remains unvisited after this process is guaranteed to be completely surrounded by sea or other trapped land.
Approach
- Initialize: Get dimensions
m,n. - Mark Escaped Land: Iterate over the boundary cells of the grid (top row, bottom row, left column, right column). If a cell is land (
1), initiate a DFS/BFS from there to mark all connected land cells as “escaped”. We can modify the inputgridin-place by changing visited escaped land cells to-1or simply treating them differently during the final count. - Count Enclaves: After processing all boundary-connected components, iterate through every cell in the grid again. Count any remaining cells that are still marked as original land (
1). These represent the enclaved regions we cannot walk off from.
Complexity Analysis
- Time Complexity: O(m * n) We visit each cell at most a constant number of times (once during boundary checks, once during traversal if connected to edge). The final count iterates over all cells again. Total operations are linear with respect to the grid size.
- Space Complexity: O(1) Auxiliary
By modifying the input
gridin-place (changing visited land to a sentinel value), we avoid allocating an extravisitedmatrix of size m*n. The recursion stack or queue for DFS/BFS uses space proportional to the maximum depth/width, which is bounded by grid dimensions but often considered O(min(m,n)) worst-case without explicit optimization; however, modifying input effectively reduces auxiliary overhead significantly compared to a separate visited set.
Solution
from typing import List
def numEnclaves(grid: List[List[int]]) -> int:
if not grid or not grid[0]:
return 0
m, n = len(grid), len(grid[0])
# Helper function for DFS traversal to mark connected land cells as visited (escaped)
def dfs(r, c):
# Check boundaries and ensure cell is still a '1' (land)
if r < 0 or r >= m or c < 0 or c >= n or grid[r][c] != 1:
return
# Mark as visited by changing to -2.
# We use -2 instead of 0 so we can distinguish from original sea (0) during traversal,
# though for the final count any non-1 is ignored anyway.
grid[r][c] = -2
# Explore all 4 directions
dfs(r + 1, c)
dfs(r - 1, c)
dfs(r, c + 1)
dfs(r, c - 1)
# Iterate over the boundary of the grid to find starting points for DFS
# Top row and Bottom row (excluding corners handled by cols loop if we want strictly unique starts,
# but iterating all boundaries is safe as duplicates don't hurt complexity).
# Left column
for r in range(m):
dfs(r, 0)
# Right column
for r in range(m):
dfs(r, n - 1)
# Top row (excluding corners to avoid redundant calls, though not strictly necessary for correctness)
for c in range(1, n - 1):
if grid[0][c] == 1:
dfs(0, c)
# Bottom row
for c in range(1, n - 1):
if grid[m-1][c] == 1:
dfs(m-1, c)
# Count remaining '1's which are the enclaves
count = 0
for r in range(m):
for c in range(n):
if grid[r][c] == 1:
count += 1
return count
Edge Cases Handled
- Single Row/Column: The boundary loops correctly handle
m=1orn=1. If a single row is all land, the loop marks them as escaped. Count returns 0 (correct). - All Land Grid: Every cell on boundary triggers DFS which floods entire grid. All become
-2. Final count is 0. Correct. - No Enclaves: Logic correctly identifies that if any
1connects to edge, it gets marked. Only isolated islands of land surrounded by sea remain as1s and are counted. - Input Modification Trade-off: The solution modifies the input grid in-place for O(1) space complexity regarding auxiliary structures (visited set). This is a standard interview trade-off; if immutability were required, we would use a separate visited matrix or hashset at cost of O(m*n) extra space.