Number of Enclaves
Problem link: https://leetcode.com/problems/number-of-enclaves/
Problem Statement
You are given an m x n binary matrix grid, where 0 represents sea and 1 represents land. 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.
Input
An m x n binary matrix grid.
Output
An integer representing the count of trapped land cells.
Example
Input: grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]] Output: 3
Explanation
The '1' at (1,0) is on the boundary. We 'sink' it. The cluster of '1's at (1,2), (2,1), and (2,2) cannot reach any edge, so they are enclaves.
Brute Force
Intuition
For every land cell, perform a DFS to see if it can reach the boundary.
Approach
- Iterate through all cells.
- If cell is '1', run DFS.
- If DFS never touches an edge, increment count.
Optimal Solution
Intuition
Reverse the logic: Sink all land that CAN reach the boundary. What remains must be an enclave.
Approach
- Loop through the boundary cells of the grid.
- If a cell is '1', use DFS to turn it and all connected land cells into '0'.
- After the boundary DFS is done, loop through the entire grid and count the remaining '1's.
Code (Java)
Complexity Analysis
Each cell is visited at most twice. Space is for the recursion stack.
Quick Revision (Brute Force)
- DFS from every land cell
- O(M*N)^2
Quick Revision (Optimal)
- Boundary DFS to sink reachable land
- Count remaining 1s
- O(M*N)