1020. Number of Enclaves

• Link: https://leetcode.com/problems/number-of-enclaves/description/

Question

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|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|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.

Approach 1: Optimal

Intuition

• Traversal from edges
• DFS

Algorithm

Code

class Solution {
public:
    const vector<pair<int, int>> directions = {
        {-1, 0}, 
        {1, 0},
        {0, -1},
        {0, 1},
    };
    void dfs(int row, int col,vector<vector<bool>>& visited, vector<vector<int>>& grid, int rows, int cols ) {

        if (row < 0 || row >= rows ||
            col < 0 || col >= cols ||
            grid[row][col] == 0 ||
            visited[row][col]) {
                return ;
            }

        visited[row][col] = true;

        for (auto direction: directions) {
            int nr = row + direction.first;
            int nc = col + direction.second;

            dfs(nr, nc, visited, grid, rows, cols);
        }
    }

    int numEnclaves(vector<vector<int>>& grid) {
        int rows = grid.size(), cols = grid[0].size();
        vector<vector<bool>> visited(rows, vector<bool>(cols, false));

        for (int i = 0 ; i < rows ; i++ ) {
            for (int j = 0 ; j < cols ; j++) {
                if ((i == 0 || i == rows - 1 ||
                    j == 0 || j == cols - 1) &&
                    grid[i][j] == 1 ) {
                        dfs(i, j, visited, grid, rows, cols);
                    }
            }
        }

        int ans = 0;

        for (int i = 0 ; i < rows ; i++ ) {
            for (int j = 0 ;j < cols ; j++) {
                if (grid[i][j] == 1 && !visited[i][j]) {
                    ans++;
                }
            }
        }

        return ans;
    }
};

Complexity Analysis

• Time Complexity: $O(n\ast m)$
• Space Complexity: $O(n\ast m)$

Approach 2: Optimal

Intuition

• Traverse from the edges of the matrix
• BFS

Algorithm

Code

class Solution {
public:
    const vector<pair<int, int>> directions = {
        {-1, 0}, {1, 0}, {0, -1}, {0, 1},
    };

    int numEnclaves(vector<vector<int>>& grid) {
        int rows = grid.size(), cols = grid[0].size();
        vector<vector<bool>> visited(rows, vector<bool>(cols, false));
        queue<pair<int, int>> q;

        // Push all boundary land cells into the queue
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if ((i == 0 || i == rows - 1 || j == 0 || j == cols - 1) && grid[i][j] == 1) {
                    q.push({i, j});
                    visited[i][j] = true; // mark immediately
                }
            }
        }

        // BFS from boundary land cells
        while (!q.empty()) {
            auto [r, c] = q.front();
            q.pop();

            for (auto [dr, dc] : directions) {
                int nr = r + dr, nc = c + dc;
                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols &&
                    grid[nr][nc] == 1 && !visited[nr][nc]) {
                    visited[nr][nc] = true; // mark visited here!
                    q.push({nr, nc});
                }
            }
        }

        // Count remaining land cells not visited
        int ans = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == 1 && !visited[i][j]) {
                    ans++;
                }
            }
        }

        return ans;
    }
};

Complexity Analysis

• Time Complexity: $O(n\ast m)$
• Space Complexity: $O(n\ast m)$