1254. Number of Closed Islands
Problem Description
The problem presents a two-dimensional grid which consists of both land (0
s) and water (1
s). An island is defined as a group of land cells (or 0
s) that are connected horizontally or vertically (4-directionally). A closed island is an island that is completely surrounded by water (1
s), meaning it does not touch the edge of the grid at any point.
The goal is to count how many closed islands are present in the grid. For example, a 0
that is at the edge of the grid could be part of an island, but since it is touching the boundary, it cannot be considered a closed island.
Flowchart Walkthrough
First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:
Is it a graph?
- Yes: The grid in the problem is akin to a graph where each cell functions as a node, and connections exist between vertically and horizontally adjacent cells.
Is it a tree?
- No: The grid is not inherently hierarchical and can contain multiple isolated groups of cells (islands), which do not form a single spanning tree.
Is the problem related to directed acyclic graphs (DAGs)?
- No: The issue revolves around finding closed structures, which is unrelated to the properties of directed acyclic graphs.
Is the problem related to shortest paths?
- No: The challenge involves identifying regions (closed islands), not determining the shortest path between points.
Does the problem involve connectivity?
- Yes: The core task is to discern and count distinct, fully enclosed land areas, which is a connectivity issue.
Does the problem have small constraints?
- Yes: Given typical grid-based problems like this, the constraints tend to be manageable, allowing for exhaustive searches.
Conclusion: The flowchart implies using DFS or backtracking for this problem due to the need for exploring all possible paths in relatively small constraints, making Depth-First Search (DFS) perfect for traversing each potential closed island thoroughly.
Intuition
To solve this problem, we can perform a depth-first search (DFS) on each cell that is land (0
). When we perform a DFS, we recursively visit each connected land cell and mark them as water (1
) to avoid revisiting them. While performing the DFS, we also check if we ever touch the boundary of the grid (i.e., the row index i
is 0 or m-1
or the column index j
is 0 or n-1
). If the DFS starts from a cell that never touches the boundary, it means we are on a closed island, and thus we should count it.
The function dfs(i, j)
is designed to perform this task, where i
and j
are the row and column indices, respectively. This function marks the current cell as visited by setting grid[i][j]
to 1
. It then checks in all four directions and calls itself (the dfs
function) on any connected land cell it finds. If any recursive call to dfs
encounters the boundary, it propagates back a failure to recognize the island as closed by returning 0
(when bitwise &
operator is applied). If an island is completely surrounded by water and doesn't touch the boundary at any point, dfs
returns 1
.
The pairwise(dirs)
function combined with the surrounding for
loop is a slight mistake in the code, possibly due to a misunderstanding of Python's itertools.pairwise, which doesn’t apply here. Instead, it should loop over pairs of directions (like (dirs[k], dirs[k + 1])
for k
in range 4) to check all four neighboring cells.
The final count of closed islands is obtained by initializing a sum with a generator expression that iterates over every cell in the grid and calls the dfs
function if a land cell (0
) is found. The result of dfs
will only be 1
for cells that are part of a closed island, and thus the sum represents the total number of closed islands in the grid.
Note: The code provided seems to have a mistake with the pairwise(dirs)
portion, which does not align with standard Python functions. The intention here might be to iterate over the directions in pairs to traverse up, right, down, and left in the grid.
Learn more about Depth-First Search, Breadth-First Search and Union Find patterns.
Solution Approach
The solution applies the depth-first search (DFS) algorithm to explore the grid and identify islands that are closed. Here's a step-by-step breakdown of the implementation:
-
Initialization: A DFS function is defined, which will be used to explore the grid. Additionally, the size of the grid is noted in variables
m
(for rows) andn
(for columns). Thedirs
array (which should contain pairs of directions to move up, right, down, and left) is used to facilitate the exploration of neighboring cells. -
Depth-First Search (DFS): The core of the solution is in the
dfs
function, which takes a cell(i, j)
and:- Marks it as visited by setting
grid[i][j] = 1
. - Checks if the cell is within the boundary but not on it, meaning
0 < i < m - 1
and0 < j < n - 1
. - Iterates in all four directions based on the
dirs
array, and if an adjoining cell is unvisited land (grid[x][y] == 0
), it recurs with these new coordinates. - If the recursive exploration touches the grid boundary, it will return 0, indicating this is not a
closed island
. If the exploration completes without touching the boundary, it returns 1, indicating aclosed island
.
- Marks it as visited by setting
-
Counting Closed Islands: The main function now initializes a sum with a generator expression that loops over each cell in the grid. It calls
dfs
on cells that are land (0
) and adds up the results. Each1
returned bydfs
denotes a closed island.
Here, it is worth noting that the "Reference Solution Approach" mentioned Union find. While the given solution does not utilize this pattern, it's relevant to acknowledge that Union find is another approach that can solve this problem. Union find, or disjoint-set data structure, would allow us to group land cells into disjoint sets and then count sets that do not touch the boundary of the grid, which effectively would identify closed islands. However, in the provided solution, DFS is used instead, which is an equally valid method for solving this problem.
The effectiveness of the DFS approach lies in its ability to mark and visit each cell only once, ensuring that the solution is efficient, with the time complexity being O(m*n), where m
is the number of rows and n
is the number of columns in the grid
. The DFS algorithm is a natural fit for problems related to navigating and exploring grids, particularly in searching for connected components, such as islands in this context.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's take a small grid as an example to illustrate how the solution approach works. Consider the following grid:
11 1 1 1 0 1 21 0 0 1 0 1 31 1 1 1 1 1 41 1 1 0 0 1 51 0 0 1 1 1 61 1 1 1 1 1
In this grid, 1
represents water and 0
represents land. We want to find how many closed islands (areas of 0
s that do not touch the grid's boundary) there are.
-
We start by defining a
dfs
function and initializing the grid size,m
andn
, respectively. In this case,m = 6
(rows) andn = 6
(columns). -
We iterate over each cell in the grid. When we come across a land cell (
0
), we start the DFS process from it by calling ourdfs
function. -
We call the
dfs
function on the land cell in the second row, second column (grid[1][1]
). The cell is marked as visited by setting it to1
. DFS checks the neighboring cells in four directions (up, down, left, right) based on a pair of directions. -
The DFS explores all connected land cells. For this example, it would change the following cells to
1
:
11 1 1 1 0 1 21 1 1 1 0 1 31 1 1 1 1 1 41 1 1 0 0 1 51 0 0 1 1 1 61 1 1 1 1 1
-
The DFS does not reach the boundary for this group of land cells, so it counts as one closed island.
-
The next unvisited land cell initiates another DFS call which is on the fourth row, fourth column (
grid[3][3]
). The process is similar; it explores connected land cells:
11 1 1 1 0 1 21 1 1 1 0 1 31 1 1 1 1 1 41 1 1 1 1 1 51 0 0 1 1 1 61 1 1 1 1 1
-
However, this time, the DFS touches the boundary at cell (
grid[4][1]
), so this island is not closed. -
The final unvisited land cell group starts at
grid[4][1]
and is similarly adjacent to the boundary.
At the end of this process, we see that only the first group of land cells (grid[1][1]
) constitutes a closed island. Thus, the final count is 1.
The DFS algorithm efficiently identified areas that constitute closed islands, ensuring no cell is visited more than once, resulting in a time complexity of O(m*n). While the pairwise(dirs)
part in the example content is confusing, the logic of the DFS here applies the correct four-directional checks by iterating over each direction pair to look at neighboring cells.
Solution Implementation
1class Solution:
2 def closedIsland(self, grid: List[List[int]]) -> int:
3 # Perform depth-first search to find and mark all cells connected to (i, j).
4 def dfs(row: int, col: int) -> int:
5 # Check if the cell is within the inner part of the grid
6 # Considering the edges can't form a closed island.
7 result = 1 if 0 < row < rows - 1 and 0 < col < cols - 1 else 0
8
9 # Mark the current cell as visited
10 grid[row][col] = 1
11
12 # Explore all four directions (up, right, down, left)
13 for direction in range(4):
14 new_row = row + directions[direction]
15 new_col = col + directions[direction + 1]
16
17 # If the new cell is within the grid and not visited
18 if 0 <= new_row < rows and 0 <= new_col < cols and grid[new_row][new_col] == 0:
19 # Continue the DFS and use logical AND to ensure all connected cells are closed
20 result &= dfs(new_row, new_col)
21 return result
22
23 # Get the number of rows and columns in the grid
24 rows, cols = len(grid), len(grid[0])
25
26 # Define the directions for the DFS. The pairs are (up, right, down, left).
27 directions = (-1, 0, 1, 0, -1)
28
29 # Initialize the count of closed islands
30 closed_islands = 0
31
32 # Iterate over each cell of the grid
33 for i in range(rows):
34 for j in range(cols):
35 # If the cell is land (0) and has not been visited
36 if grid[i][j] == 0:
37 # Perform DFS from the current cell and check if it forms a closed island
38 closed_islands += dfs(i, j)
39
40 # Return the total count of closed islands
41 return closed_islands
42
1class Solution {
2 private int height; // Variable to store the height of the grid
3 private int width; // Variable to store the width of the grid
4 private int[][] grid; // 2D array to represent the grid itself
5
6 // Function to count the number of closed islands in the grid
7 public int closedIsland(int[][] grid) {
8 height = grid.length; // Set the height of the grid
9 width = grid[0].length; // Set the width of the grid
10 this.grid = grid; // Assign the grid argument to the instance variable
11 int count = 0; // Initialize count of closed islands
12
13 // Iterate over each cell in the grid
14 for (int i = 0; i < height; ++i) {
15 for (int j = 0; j < width; ++j) {
16 // If the current cell is 0 (land), perform a DFS to mark the connected components
17 if (grid[i][j] == 0) {
18 count += dfs(i, j); // Increment count if the land is part of a closed island
19 }
20 }
21 }
22 return count; // Return the total number of closed islands
23 }
24
25 // Helper method to perform DFS and determine if a connected component is a closed island
26 private int dfs(int row, int col) {
27 // If not on the border, assume it's a closed island; otherwise, it's not
28 int isClosed = (row > 0 && row < height - 1 && col > 0 && col < width - 1) ? 1 : 0;
29 grid[row][col] = 1; // Mark the current cell as visited by setting it to 1
30 int[] directions = {-1, 0, 1, 0, -1}; // Array to help traverse in 4 cardinal directions
31
32 // Explore all 4 adjacent cells
33 for (int k = 0; k < 4; ++k) {
34 int nextRow = row + directions[k]; // Calculate the next row index
35 int nextCol = col + directions[k + 1]; // Calculate the next column index
36 // Verify if the adjacent cell is within the grid and if it is land (0)
37 if (nextRow >= 0 && nextRow < height && nextCol >= 0 && nextCol < width
38 && grid[nextRow][nextCol] == 0) {
39 // Perform DFS on the adjacent cell and use logical AND to update the isClosed status
40 isClosed &= dfs(nextRow, nextCol); // If any part touches the border, it's not closed
41 }
42 }
43 return isClosed; // Return 1 if the island is closed, otherwise 0
44 }
45}
46
1class Solution {
2public:
3 int closedIsland(vector<vector<int>>& grid) {
4 // Get the number of rows and columns in the grid.
5 int rowCount = grid.size(), colCount = grid[0].size();
6
7 // Initialize the count of closed islands to zero.
8 int closedIslandCount = 0;
9
10 // Define directions for traversing the grid (up, right, down, left).
11 int directions[5] = {-1, 0, 1, 0, -1};
12
13 // Define a recursive Depth-First Search (DFS) lambda function to find closed islands.
14 function<int(int, int)> depthFirstSearch = [&](int row, int col) -> int {
15 // If the current cell is surrounded by non-border cells, mark as potential closed island.
16 int isClosedIsland = (row > 0 && row < rowCount - 1 && col > 0 && col < colCount - 1) ? 1 : 0;
17
18 // Mark the current cell as visited.
19 grid[row][col] = 1;
20
21 // Explore all 4 directions.
22 for (int k = 0; k < 4; ++k) {
23 int nextRow = row + directions[k], nextCol = col + directions[k + 1];
24 // If the next cell is on the grid and unvisited, continue the DFS.
25 if (nextRow >= 0 && nextRow < rowCount && nextCol >= 0 && nextCol < colCount && grid[nextRow][nextCol] == 0) {
26 // If any recursive DFS call returns 0, then it's not a closed island.
27 isClosedIsland &= depthFirstSearch(nextRow, nextCol);
28 }
29 }
30 // Return whether the current cell is part of a closed island.
31 return isClosedIsland;
32 };
33
34 // Loop over all cells in the grid.
35 for (int i = 0; i < rowCount; ++i) {
36 for (int j = 0; j < colCount; ++j) {
37 // If the cell is land (0) and the DFS returns true for a closed island, increment the count.
38 closedIslandCount += (grid[i][j] == 0 && depthFirstSearch(i, j));
39 }
40 }
41
42 // Return the total count of closed islands found.
43 return closedIslandCount;
44 }
45};
46
1// Function to calculate the number of closed islands in a grid.
2// A closed island is a group of connected 0s that is completely surrounded by 1s (representing water),
3// and does not touch the edge of the grid.
4// @param grid - The 2D grid of 0s (land) and 1s (water).
5// @returns The count of closed islands.
6function closedIsland(grid: number[][]): number {
7 // Store the dimensions of the grid.
8 const rowCount = grid.length;
9 const colCount = grid[0].length;
10 // Directions for traversing up, down, left, and right in the grid.
11 const directions = [-1, 0, 1, 0, -1];
12 // DFS function to explore the cells in the grid.
13 const depthFirstSearch = (row: number, col: number): number => {
14 // A flag to indicate if the current island is closed.
15 // It's closed only if it doesn't touch the grid's edge.
16 let isClosed = row > 0 && col > 0 && row < rowCount - 1 && col < colCount - 1 ? 1 : 0;
17 // Mark the cell as visited by setting it to 1.
18 grid[row][col] = 1;
19 // Explore all 4 adjacent directions (up, down, left, right).
20 for (let k = 0; k < 4; ++k) {
21 const newRow = row + directions[k];
22 const newCol = col + directions[k + 1];
23 // Check if the new cell is within bounds and is land (0).
24 if (newRow >= 0 && newCol >= 0 && newRow < rowCount && newCol < colCount && grid[newRow][newCol] === 0) {
25 // If any recursive call returns 0, the island isn't closed.
26 isClosed &= depthFirstSearch(newRow, newCol);
27 }
28 }
29 // Return whether the island is closed.
30 return isClosed;
31 };
32
33 // Initialize the count of closed islands.
34 let closedIslandsCount = 0;
35 // Iterate through all cells in the grid.
36 for (let row = 0; row < rowCount; ++row) {
37 for (let col = 0; col < colCount; col++) {
38 // If a cell is land and unvisited, perform DFS.
39 if (grid[row][col] === 0) {
40 closedIslandsCount += depthFirstSearch(row, col);
41 }
42 }
43 }
44 // Return the final count of closed islands.
45 return closedIslandsCount;
46}
47
Time and Space Complexity
The given Python code is a solution for finding the number of "closed islands" in a 2D grid, where 0
represents land and 1
represents water. A "closed island" is one that is surrounded by water and doesn't touch the edge of the grid. The algorithm uses Depth-First Search (DFS) to explore the grid.
Time Complexity
The time complexity of the code is O(m * n)
, where m
is the number of rows and n
is the number of columns in the grid. This is because the algorithm potentially visits each cell in the grid once. The DFS is started only if the current cell is a 0
(land), and then it marks every visited land cell as 1
(water) to prevent revisiting. In the worst case, all cells in the grid will be traversed once.
Space Complexity
The space complexity of the DFS is O(m * n)
in the worst case. This might happen when the depth of the recursion stack grows proportionally to the number of cells in the worst-case scenario, such as when the grid forms a large area of contiguous land. The space is used by the recursion call stack during the depth-first search.
However, if we consider that modern Python implementations use a technique called "tail-recursion elimination" in some cases, the space complexity can be effectively less than O(m * n)
for some grids because not all calls will result in an additional stack frame. But in the analysis of DFS, it is conventional to consider the worst-case scenario regarding recursion.
The additional space used by the dirs
variable and a few integer variables is negligible compared to the recursive stack space, thus not affecting the overall space complexity.
Learn more about how to find time and space complexity quickly using problem constraints.
The three-steps of Depth First Search are:
- Identify states;
- Draw the state-space tree;
- DFS on the state-space tree.
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS
https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell
Union Find Disjoint Set Union Data Structure Introduction Prerequisite Depth First Search Review problems dfs_intro Once we have a strong grasp of recursion and Depth First Search we can now introduce Disjoint Set Union DSU This data structure is motivated by the following problem Suppose we have sets of elements
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.