Problem Statement
You are given an N x M binary matrix grid, where:
0represents sea.1represents land.
You can move 4-directionally (up, down, left, or right) from one land cell to another. If a land cell is part of a group of connected land cells that can reach the boundary of the grid, then it's possible to walk off the boundary starting from that cell. You are asked to find the number of land cells for which it is impossible to walk off the boundary of the grid.
In other words, you are required to find the number of enclaves, which are land cells that are surrounded by sea and not connected to any boundary.
A land cell is considered safe if it's not connected to the boundary, meaning it forms an enclave. The task is to count the number of land cells that are safe.
An enclave is defined as a group of connected 1s (land) such that no part of this group is connected to the boundary (i.e., any grid[i][j] where i == 0, i == n-1, j == 0, or j == m-1). You are asked to find the number of land cells that belong to these enclaves.
Examples
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 2 connected components of land. The component on the right (at positions (1, 2) and (2, 2)) is not connected to the boundary, forming an enclave. The land cells forming enclaves are (1, 2), (2, 1), and (2, 2) for a total of 3 land cells.
Example 2:
Input: grid = [
[0, 1, 1, 0],
[1, 0, 1, 0],
[0, 0, 1, 0],
[0, 0, 0, 0]
]
Output: 0
Example:
There is only one connected component of land, but it touches the boundary, so no cells are part of an enclave. Theory
The key idea to solve the problem is to remove any land cells that can reach the boundary. Any land connected to the boundary cannot be an enclave, so we can mark those cells as visited and ignore them.
Steps:
- Identify Boundary Connected Lands: Perform a DFS or BFS on all land cells connected to the boundary and mark them as visited.
- Count Remaining Land Cells: Once all boundary-connected lands are removed, count the remaining unvisited land cells.
Different Approaches
1️⃣ BFS (Breadth-First Search)
Instead of using recursion, BFS uses an iterative approach, making it easier on the call stack.
Algorithm:
- Process boundary cells:
- Start BFS from each land cell on the boundary and mark all reachable land cells as visited.
- Count remaining land cells:
- After the BFS traversal, count all remaining unmarked land cells.
Code:
class Solution {
public:
// Helper function to check if a cell (row, col) is within the grid boundaries.
bool valid(int row, int col, int n, int m) {
// Check if row index is out of bounds.
if (row < 0 || row >= n) {
return false;
}
// Check if column index is out of bounds.
if (col < 0 || col >= m) {
return false;
}
return true;
}
// Function to count the number of enclaves (land cells not reachable from the boundary).
int numberOfEnclaves(vector<vector<int>> &grid) {
int n = grid.size(); // Number of rows.
int m = grid[0].size(); // Number of columns.
// Create a visited matrix initialized with 0 (false) for all cells.
vector<vector<int>> vis(n, vector<int>(m, 0));
// Direction vectors for the four cardinal directions: up, right, down, left.
int dx[4] = {-1, 0, 1, 0};
int dy[4] = { 0, 1, 0, -1};
// Process all boundary cells.
for (int row = 0; row < n; row++) {
for (int col = 0; col < m; col++) {
// Check if the cell is on the boundary.
if ((row == 0 || row == n - 1) || (col == 0 || col == m - 1)) {
// If it is water (0) or already visited, skip it.
if (grid[row][col] == 0 || vis[row][col] == 1) {
continue;
}
// Create a queue for BFS. Each element is a pair (row, col).
queue<pair<int, int>> que;
// Push the boundary cell and mark it as visited.
que.push({row, col});
vis[row][col] = 1;
// Perform BFS to mark all land cells connected to this boundary cell.
while (!que.empty()) {
pair<int, int> front = que.front();
que.pop();
int x = front.first;
int y = front.second;
// Check all four neighbors.
for (int i = 0; i < 4; i++) {
int posX = x + dx[i];
int posY = y + dy[i];
// Ensure neighbor indices are valid, not visited, and are land (1).
if (valid(posX, posY, n, m) && !vis[posX][posY] && grid[posX][posY] == 1) {
vis[posX][posY] = 1; // Mark neighbor as visited.
que.push({posX, posY}); // Push neighbor into the queue for further processing.
}
}
}
}
}
}
// After BFS from all boundaries, count the number of enclaves.
// Enclaves are land cells (1) that were never visited (vis == 0).
int count = 0;
for (int row = 0; row < n; row++) {
for (int col = 0; col < m; col++) {
if (grid[row][col] == 1 && vis[row][col] == 0) {
count++;
}
}
}
return count;
}
};Complexity Analysis:
- Time Complexity: O(N*M) (where N and M are the dimensions of image)
- In the worst case, all the cell will have land, and BFS call will be made for (N*M) nodes.
- For every cell, its four neighbors are traversed, taking O(4*N*M) time.
- Space Complexity: O(N*M)
- Visited array takes O(N*M) space.
- In worst scenario, the queue takes up O(N*M) space.
2️⃣ DFS (Depth-First Search)
The idea is to traverse the boundary of the grid and mark all land cells that can reach the boundary. Any land cell that is not marked will be considered an enclave.
Steps:
- Traverse the boundary:
- Perform DFS starting from all boundary land cells (cells on the first/last row or first/last column) and mark all reachable land cells as visited.
- Count Remaining Land Cells:
- After marking all boundary-connected land cells, traverse the grid again and count all unmarked land cells. These are enclaves.
Code:
class Solution {
public:
// Helper function to check if a cell (row, col) is within grid boundaries.
bool valid(int row, int col, int n, int m) {
// Return false if row index is out of bounds.
if (row < 0 || row >= n) {
return false;
}
// Return false if column index is out of bounds.
if (col < 0 || col >= m) {
return false;
}
return true;
}
// Direction vectors for the four cardinal directions: up, right, down, left.
int dx[4] = {-1, 0, 1, 0};
int dy[4] = { 0, 1, 0, -1};
// DFS function to traverse all connected land cells starting from (row, col).
// It marks visited cells in the 'vis' matrix.
void dfs(vector<vector<int>>& grid, vector<vector<int>>& vis, int row, int col, int n, int m) {
// Mark the current cell as visited.
vis[row][col] = 1;
// Check all four neighboring cells.
for (int i = 0; i < 4; i++) {
int posX = row + dx[i];
int posY = col + dy[i];
// Process the neighbor if it's within bounds, not yet visited, and is land (1).
if (valid(posX, posY, n, m) && !vis[posX][posY] && grid[posX][posY] == 1) {
dfs(grid, vis, posX, posY, n, m);
}
}
}
// Function to count the number of enclaves.
// Enclaves are land cells (1) that are not reachable from the boundary.
int numberOfEnclaves(vector<vector<int>> &grid) {
int n = grid.size(); // Number of rows in the grid.
int m = grid[0].size(); // Number of columns in the grid.
// Create a visited matrix initialized with 0 (false) for all cells.
vector<vector<int>> vis(n, vector<int>(m, 0));
// Process all boundary cells.
for (int row = 0; row < n; row++) {
for (int col = 0; col < m; col++) {
// Check if the cell is on the boundary.
if ((row == 0 || row == n - 1) || (col == 0 || col == m - 1)) {
// If it is water (0) or already visited, skip processing.
if (grid[row][col] == 0 || vis[row][col] == 1) {
continue;
}
// Start DFS from this boundary land cell to mark all reachable land cells.
dfs(grid, vis, row, col, n, m);
}
}
}
// After marking all boundary-connected land cells,
// count the number of enclaves (land cells not visited).
int count = 0;
for (int row = 0; row < n; row++) {
for (int col = 0; col < m; col++) {
if (grid[row][col] == 1 && vis[row][col] == 0) {
count++;
}
}
}
return count;
}
};
Complexity Analysis:
- Time Complexity: O(N*M) (where N and M are the dimensions of image)
- In the worst case, all the cell will have land, and BFS call will be made for (N*M) nodes.
- For every cell, its four neighbors are traversed, taking O(4*N*M) time.
- Space Complexity: O(N*M)
- Visited array takes O(N*M) space.
- In worst scenario, the queue takes up O(N*M) space.