Number of Enclaves

Link

Description

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.length
• n == grid[i].length
• 1 <= m, n <= 500
• grid[i][j] is either 0 or 1.

Solution

class Solution {
private:
    int m, n;
    int dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 0};

    void dfs(vector<vector<int>>& grid, int x, int y) {
        if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] != 1) return;
        grid[x][y] = 0;
        for (int i = 0; i < 4; i++) {
            dfs(grid, x + dx[i], y + dy[i]);
        }
    }

public:
    int numEnclaves(vector<vector<int>>& grid) {
        m = grid.size(); n = grid[0].size();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || j == 0 || i == m - 1 || j == n - 1)
                    dfs(grid, i, j);
            }
        }
        return accumulate(begin(grid), end(grid), 0, [](int s, vector<int>& r) {
            return s + accumulate(begin(r), end(r), 0);
        });
    }
};

Steps:

• Identify and Mark Boundary-Reaching Land: Use DFS to explore and mark all the land cells (value 1) that can reach the boundary. This is done by starting DFS from all boundary cells that are land.
• Count Remaining Land Cells: After the boundary-reaching land cells are marked (set to 0), count the remaining land cells (still with value 1) in the grid.

Another way of writing:

class Solution {
private:
    int m, n;
    int dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 0};

    void dfs(vector<vector<int>>& grid, int x, int y) {
        if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] != 1) return;
        grid[x][y] = 0;
        for (int i = 0; i < 4; i++) {
            dfs(grid, x + dx[i], y + dy[i]);
        }
    }

public:
    int numEnclaves(vector<vector<int>>& grid) {
        m = grid.size(); n = grid[0].size();
        for (int i = 0; i < m; i++) {
            dfs(grid, i, 0);
            dfs(grid, i, n - 1);
        }
        for (int j = 1; j < n - 1; j++) {
            dfs(grid, 0, j);
            dfs(grid, m - 1, j);
        }

        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;
    }
};

Analyzing the time and space complexity:

Time Complexity:

1. DFS Calls on Boundary Cells: The DFS function is called for each boundary cell in the grid. The grid is of size \(m\times n\), where \(m\) is the number of rows, and \(n\) is the number of columns. There are \(2m + 2(n - 2)\) boundary cells (top row, bottom row, and leftmost and rightmost columns without the corners). However, this count is not the major factor in time complexity, as not all boundary cells will necessarily trigger deep DFS calls.
2. DFS Function: Each DFS call can potentially visit all cells in the worst case, if the grid is filled with land cells ('1'). However, once a cell is visited, it is marked as '0', ensuring that each cell is visited at most once across all DFS calls. This means, in total, the DFS traversal will look at each cell in the grid once. Hence, the DFS traversal's time complexity is \(O(mn)\).
3. Counting Remaining Cells: The final count of enclaves involves iterating over the entire grid again. This is also \(O(mn)\).

Therefore, the overall time complexity of the algorithm is \(O(mn)\), where \(m\) is the number of rows and \(n\) is the number of columns in the grid.

Space Complexity:

1. Recursive DFS Stack: The space complexity mainly comes from the DFS recursion stack. In the worst case, if the grid is filled with land cells, the DFS can go as deep as \(mn\) (the entire grid), but this would be an extreme and unlikely case. A more realistic worst-case scenario is proportional to the smaller of \(m\) and \(n\), as the DFS would traverse either the length or width of the grid in the deepest recursive call. Thus, we can consider the space complexity due to recursion as \(O(\min (m, n))\).
2. No Additional Data Structures: Aside from the recursion stack, the algorithm does not use any significant extra space. The grid is modified in place.