1020. Number of Enclaves

📝 Problem Details

• Title: 1020. Number of Enclaves
• Link: https://leetcode.com/problems/number-of-enclaves/
• Difficulty: Medium
• Tags/Categories: DFS Matrix

input m x n binary matrix grid 0 represents sea / water 1 represents land return the number of land cells in grid for which we cannot walk off the boundary of the grid in any number of moves

💡 Explanation of Solution

from each boundary cell:
- perform DFS in every direction while the cell value is == 1 (land)
- this represents every cell has can have a walk off the boundary
	- mark them inplace
- second iteration, this time through the entire grid, counting the remaining 1s
- return that count 

⌛ Complexity Analysis

Time Complexity: O(m * n) 
- we arent revisiting cells 

Space Complexity: O(m * n)
recursive call stack 

💻 Implementation of Solution

```cpp
class Solution {
public:
    void dfs(vector<vector<int>>& grid, int r, int c, int rows, int cols) {
        if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] == 0) return;
 
        grid[r][c] = 0;
 
        dfs(grid, r + 1, c, rows, cols);
        dfs(grid, r - 1, c, rows, cols);
        dfs(grid, r, c + 1, rows, cols);
        dfs(grid, r, c - 1, rows, cols);
    }
 
    int numEnclaves(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
 
        // Traverse the boundary and perform DFS to sink all land connected to edge
        for (int i = 0; i < m; i++) {
            dfs(grid, i, 0, m, n);       // left column
            dfs(grid, i, n - 1, m, n);   // right column
        }
 
        for (int j = 0; j < n; j++) {
            dfs(grid, 0, j, m, n);       // top row
            dfs(grid, m - 1, j, m, n);   // bottom row
        }
 
        // Count remaining land cells
        int count = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) count++;
            }
        }
        return count;
    }
};