Number of Closed Islands
MedPrompt
Given a 2D grid consists of 0s (land) and 1s (water). An island is a maximal 4-directionally connected group of 0s and a closed island is an island totally (all left, top, right, bottom) surrounded by 1s.
Return the number of closed islands.
Example 1:
Input: grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]]
Output: 2
Explanation:
Islands in gray are closed because they are completely surrounded by water (group of 1s).Example 2:
Input: grid = [[0,0,1,0,0],[0,1,0,1,0],[0,1,1,1,0]]
Output: 1Example 3:
Input: grid = [[1,1,1,1,1,1,1],
[1,0,0,0,0,0,1],
[1,0,1,1,1,0,1],
[1,0,1,0,1,0,1],
[1,0,1,1,1,0,1],
[1,0,0,0,0,0,1],
[1,1,1,1,1,1,1]]
Output: 2
Constraints:
1 <= grid.length, grid[0].length <= 1000 <= grid[i][j] <=1
Approaches
2 approaches with complexity analysis and trade-offs.
This approach iterates through the grid to find the start of a potential island (a '0'). Once an unvisited land cell is found, it initiates a traversal (like Depth First Search or Breadth First Search) to find all connected land cells that form the island. During the traversal, it checks if any cell of the island lies on the grid's boundary. If no cell touches the boundary after the entire island is explored, it's counted as a closed island. A separate visited array is used to keep track of visited cells to avoid redundant work.
Algorithm
- Initialize
count = 0. - Create a
visited2D array of the same dimensions asgrid, initialized tofalse. - Iterate through each cell
(i, j)in thegrid. - If
grid[i][j] == 0andvisited[i][j]isfalse:- This is a new island. Initialize a boolean flag
isCurrentIslandClosed = true. - Start a traversal (DFS/BFS) from
(i, j). - During traversal, mark visited cells in the
visitedarray. - If any cell of the island is on the grid boundary (i.e.,
i=0,i=rows-1,j=0, orj=cols-1), setisCurrentIslandClosed = false. - After the traversal for the current island is complete, if
isCurrentIslandClosedistrue, incrementcount.
- This is a new island. Initialize a boolean flag
- Return
count.
Walkthrough
We'll use a 2D visited array to keep track of cells we've already processed. We iterate through every cell (i, j) of the grid. If we find a land cell (grid[i][j] == 0) that has not been visited (visited[i][j] == false), we know we've found a new island. We then start a DFS from this cell. The DFS will explore the entire island and simultaneously check if it's a closed island. We use a boolean flag, isClosed, initialized to true before starting the DFS for a new island. The DFS function will be designed to turn this flag to false if it ever encounters a cell on the grid's border.
The DFS function takes the current cell's coordinates (r, c) as input. It first checks for boundary conditions for the island itself. If the current cell (r, c) is on the border of the grid, it means the island is not closed, so we set isClosed = false. It marks the current cell as visited and then recursively calls itself for all 4-directionally adjacent land cells. After the DFS for the island is complete, we check the isClosed flag. If it's still true, we increment our count of closed islands. This process continues until all cells in the grid have been visited.
class Solution { private boolean isClosed; private int rows, cols; private int[][] grid; private boolean[][] visited; public int closedIsland(int[][] grid) { this.grid = grid; this.rows = grid.length; this.cols = grid[0].length; this.visited = new boolean[rows][cols]; int closedIslandCount = 0; for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { if (grid[i][j] == 0 && !visited[i][j]) { // Found a new island, check if it's closed isClosed = true; dfs(i, j); if (isClosed) { closedIslandCount++; } } } } return closedIslandCount; } private void dfs(int r, int c) { // Base cases for stopping the recursion if (r < 0 || r >= rows || c < 0 || c >= cols || visited[r][c] || grid[r][c] == 1) { return; } // If a land cell is on the border, the island is not closed if (r == 0 || r == rows - 1 || c == 0 || c == cols - 1) { isClosed = false; } visited[r][c] = true; // Explore neighbors dfs(r + 1, c); dfs(r - 1, c); dfs(r, c + 1); dfs(r, c - 1); }}Complexity
Time
O(M * N), where M is the number of rows and N is the number of columns. Each cell is visited a constant number of times.
Space
O(M * N) for the `visited` array and the recursion stack in the worst-case scenario, where M is the number of rows and N is the number of columns.
Trade-offs
Pros
Conceptually straightforward, directly follows the problem definition.
Cons
Requires an auxiliary
visitedarray, which consumes extra space.The traversal logic is coupled with the boundary checking logic, which can be slightly less clean than separating the concerns.
This is a more elegant and often preferred approach. The core idea is that any island connected to the border of the grid cannot be a closed island. We can first eliminate all such islands. This is done by iterating over the border cells of the grid. If a border cell is land ('0'), we start a traversal (DFS/BFS) from it and "sink" all connected land cells by changing their value to '1' (water). After this first pass, any remaining '0's in the grid must belong to closed islands. A second pass is then made to count these remaining islands.
Algorithm
- Get grid dimensions
rowsandcols. - First Pass:
- Iterate through the cells on the top and bottom borders (
i=0,i=rows-1). If a cell is land (0), start a traversal (DFS/BFS) to find all connected land cells and change them to water (1). - Iterate through the cells on the left and right borders (
j=0,j=cols-1). If a cell is land (0), do the same traversal and sinking process.
- Iterate through the cells on the top and bottom borders (
- Second Pass:
- Initialize
count = 0. - Iterate through the inner cells of the grid (from
(1,1)to(rows-2, cols-2)). - If a cell
(i, j)is land (0):- Increment
count. - Start a traversal from
(i, j)to sink this entire island (change all its0s to1s) to prevent recounting.
- Increment
- Initialize
- Return
count.
Walkthrough
The problem is simplified by first removing all islands that are guaranteed not to be closed. An island is not closed if any of its land cells touch the grid's border.
Pass 1: Sink non-closed islands.
We iterate along the four borders of the grid (top row, bottom row, left column, right column). Whenever we find a land cell (grid[i][j] == 0) on a border, we know it's part of a non-closed island. We start a DFS from this cell. The purpose of this DFS is to find all connected land cells and change their value from 0 to 1. This effectively "sinks" the entire island, removing it from consideration. We can modify the grid in-place.
Pass 2: Count remaining islands.
After the first pass, the grid has been modified. All 0s connected to the border are now 1s. Any 0 that still exists in the grid must be part of an island completely surrounded by 1s, i.e., a closed island. We now perform a standard "count islands" algorithm on the modified grid. We iterate through every cell (i, j). If we find a grid[i][j] == 0, we've found a new closed island. We increment our counter. To avoid counting the same island again, we immediately "sink" this newly found island by starting another DFS from (i, j) to change all its connected 0s to 1s.
This two-pass approach neatly separates the logic of identifying and counting closed islands.
class Solution { public int closedIsland(int[][] grid) { int rows = grid.length; int cols = grid[0].length; // Pass 1: Sink all land cells connected to the border. // These are part of non-closed islands. for (int i = 0; i < rows; i++) { // Left border if (grid[i][0] == 0) { dfs(i, 0, grid); } // Right border if (grid[i][cols - 1] == 0) { dfs(i, cols - 1, grid); } } for (int j = 0; j < cols; j++) { // Top border if (grid[0][j] == 0) { dfs(0, j, grid); } // Bottom border if (grid[rows - 1][j] == 0) { dfs(rows - 1, j, grid); } } // Pass 2: Count the remaining islands. // Any '0' left is part of a closed island. int closedIslandCount = 0; for (int i = 1; i < rows - 1; i++) { for (int j = 1; j < cols - 1; j++) { if (grid[i][j] == 0) { closedIslandCount++; dfs(i, j, grid); // Sink this island to not recount it } } } return closedIslandCount; } private void dfs(int r, int c, int[][] grid) { int rows = grid.length; int cols = grid[0].length; if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] == 1) { return; } // Sink the land cell grid[r][c] = 1; // Explore neighbors dfs(r + 1, c, grid); dfs(r - 1, c, grid); dfs(r, c + 1, grid); dfs(r, c - 1, grid); }}Complexity
Time
O(M * N), where M is the number of rows and N is the number of columns. The grid is traversed at most twice, and each cell is processed a constant number of times across all DFS calls.
Space
O(M * N) in the worst case for the recursion stack depth. This approach modifies the grid in-place, so it doesn't require an additional `visited` array.
Trade-offs
Pros
More efficient in practice as it avoids a separate
visitedarray.The logic is cleaner, separating the problem into two distinct, simpler subproblems: eliminating non-closed islands and then counting the remaining ones.
Modifying the input grid is a common and accepted technique for this class of problems.
Cons
Modifies the input grid, which might not be permissible in all contexts. If the original grid must be preserved, a copy would be needed, increasing space complexity.
Solutions
Solution
public class Solution { private int m; private int n; private int[][] grid; public int ClosedIsland(int[][] grid) { m = grid.Length; n = grid[0].Length; this.grid = grid; int ans = 0; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (grid[i][j] == 0) { ans += dfs(i, j); } } } return ans; } private int dfs(int i, int j) { int res = i > 0 && i < m - 1 && j > 0 && j < n - 1 ? 1 : 0; grid[i][j] = 1; int[] dirs = { -1, 0, 1, 0, -1 }; for (int k = 0; k < 4; ++k) { int x = i + dirs[k], y = j + dirs[k + 1]; if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 0) { res &= dfs(x, y); } } return res; }}class Solution {private int m;private int n;private int[][] grid;public int closedIsland(int[][] grid) { m = grid.length; n = grid[0].length; this.grid = grid; int ans = 0; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (grid[i][j] == 0) { ans += dfs(i, j); } } } return ans; }private int dfs(int i, int j) { int res = i > 0 && i < m - 1 && j > 0 && j < n - 1 ? 1 : 0; grid[i][j] = 1; int[] dirs = {-1, 0, 1, 0, -1}; for (int k = 0; k < 4; ++k) { int x = i + dirs[k], y = j + dirs[k + 1]; if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 0) { res &= dfs(x, y); } } return res; }}class Solution {public: int closedIsland(vector<vector<int>> &grid) { int m = grid.size(), n = grid[0].size(); int ans = 0; int dirs[5] = {-1, 0, 1, 0, -1}; function<int(int, int)> dfs = [&](int i, int j) -> int { int res = i > 0 && i < m - 1 && j > 0 && j < n - 1 ? 1 : 0; grid[i][j] = 1; for (int k = 0; k < 4; ++k) { int x = i + dirs[k], y = j + dirs[k + 1]; if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 0) { res &= dfs(x, y); } } return res; }; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { ans += grid[i][j] == 0 && dfs(i, j); } } return ans; }};class Solution: def closedIsland(self, grid: List[List[int]]) -> int: def dfs(i: int, j: int) -> int: res = int(0 < i < m - 1 and 0 < j < n - 1) grid[i][j] = 1 for a, b in pairwise(dirs): x, y = i + a, j + b if 0 <= x < m and 0 <= y < n and grid[x][y] == 0: res &= dfs(x, y) return res m, n = len(grid), len(grid[0]) dirs = (- 1, 0, 1, 0, - 1) return sum(grid[i][j] == 0 and dfs(i, j) for i in range(m) for j in range(n))Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.