In this guide, you will get 1020. Number of Enclaves LeetCode Solution with the best time and space complexity. The solution to Number of Enclaves problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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.
Complexity Analysis
Time Complexity: O(mn)
Space Complexity: O(mn)
1020. Number of Enclaves LeetCode Solution in C++
class Solution {
public:
int numEnclaves(vector<vector<int>>& grid) {
const int m = grid.size();
const int n = grid[0].size();
// Remove the lands connected to the edge.
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (i * j == 0 || i == m - 1 || j == n - 1)
if (grid[i][j] == 1)
dfs(grid, i, j);
return accumulate(grid.begin(), grid.end(), 0,
[](int subtotal, vector<int>& row) {
return subtotal + accumulate(row.begin(), row.end(), 0);
});
}
private:
void dfs(vector<vector<int>>& grid, int i, int j) {
if (i < 0 || i == grid.size() || j < 0 || j == grid[0].size())
return;
if (grid[i][j] == 0)
return;
grid[i][j] = 0;
dfs(grid, i + 1, j);
dfs(grid, i - 1, j);
dfs(grid, i, j + 1);
dfs(grid, i, j - 1);
};
}; /* code provided by PROGIEZ */
1020. Number of Enclaves LeetCode Solution in Java
class Solution {
public int numEnclaves(int[][] grid) {
final int m = grid.length;
final int n = grid[0].length;
// Remove the lands connected to the edge.
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (i * j == 0 || i == m - 1 || j == n - 1)
if (grid[i][j] == 1)
dfs(grid, i, j);
return Arrays.stream(grid).flatMapToInt(Arrays::stream).sum();
}
private void dfs(int[][] grid, int i, int j) {
if (i < 0 || i == grid.length || j < 0 || j == grid[0].length)
return;
if (grid[i][j] == 0)
return;
grid[i][j] = 0;
dfs(grid, i + 1, j);
dfs(grid, i - 1, j);
dfs(grid, i, j + 1);
dfs(grid, i, j - 1);
}
} // code provided by PROGIEZ
1020. Number of Enclaves LeetCode Solution in Python
