Leetcode 1254: Number of Closed Islands
You are given a 2D grid with 0s (land) and 1s (water). An island is a group of 0s connected 4-directionally, and a closed island is a group of 0s completely surrounded by 1s. Your task is to count how many closed islands are present in the grid.
Problem
Approach
Steps
Complexity
Input: The input consists of a 2D grid with 0s and 1s.
Example: 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]]
Constraints:
• 1 <= grid.length, grid[0].length <= 100
• 0 <= grid[i][j] <= 1
Output: The output is a single integer representing the number of closed islands.
Example: Output: 2
Constraints:
• The number of closed islands can be at least 0.
Goal: The goal is to count the number of closed islands in the grid.
Steps:
• Loop through the grid, marking water cells connected to the boundary.
• Perform a depth-first search (DFS) to explore each closed island.
• Count each closed island and ensure no boundary cell is part of a closed island.
Goal: The grid dimensions are within 1 to 100 rows and columns.
Steps:
• 1 <= grid.length, grid[0].length <= 100
• 0 <= grid[i][j] <= 1
Assumptions:
• The grid is composed of only 0s and 1s.
• Boundary cells are considered to be part of the outer boundary.
• Input: Input: [[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]]
• Explanation: The grid contains two closed islands, both of which are surrounded by water.
Approach: The approach involves marking and counting the closed islands in the grid using a depth-first search (DFS).
Observations:
• Boundary cells cannot be part of a closed island.
• Each land cell that is connected to the boundary must be marked as water to avoid counting non-closed islands.
• DFS is a suitable technique to explore all connected land cells of an island.
Steps:
• Mark boundary-connected land cells as water.
• For each unvisited land cell, perform DFS to check if it forms a closed island.
• Count and return the number of closed islands.
Empty Inputs:
• Empty grids should return 0.
Large Inputs:
• Grids with the maximum size (100x100) should be handled efficiently.
Special Values:
• Grids with no water cells should return 0.
Constraints:
• Ensure that the grid size is within the specified limits.
int closedIsland(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
for(int i = 0; i < m; i++)
for(int j = 0; j < n; j++)
if(i == 0 || j == 0 || i == m - 1 || j == n - 1)
if(grid[i][j] == 0)
dfs(grid, i, j, 0, 1);
int cnt = 0;
for(int i = 0; i < m; i++)
for(int j = 0; j < n; j++)
if(grid[i][j] == 0) {
dfs(grid, i, j, 0, cnt + 2);
cnt++;
}
return cnt;
}
void dfs(vector<vector<int>>& grid, int i, int j, int cur, int tgt) {
int m = grid.size(), n = grid[0].size();
if(i < 0 || j < 0 || i == m || j == n || grid[i][j] != cur)
return;
grid[i][j] = tgt;
dfs(grid, i + 1, j, cur, tgt);
dfs(grid, i, j + 1, cur, tgt);
dfs(grid, i - 1, j, cur, tgt);
dfs(grid, i, j - 1, cur, tgt);
}
1 : Function Definition
int closedIsland(vector<vector<int>>& grid) {
The function `closedIsland` is defined to take a 2D grid as input, where each cell is either land (1) or water (0). The goal is to find the number of closed islands (i.e., islands surrounded by water).
2 : Variable Initialization
int m = grid.size(), n = grid[0].size();
The variables `m` and `n` are initialized to the number of rows and columns of the grid, respectively.
3 : Outer Loop
for(int i = 0; i < m; i++)
An outer loop starts that iterates over the rows of the grid.
4 : Inner Loop
for(int j = 0; j < n; j++)
An inner loop iterates over the columns of the grid for each row.
5 : Boundary Check
if(i == 0 || j == 0 || i == m - 1 || j == n - 1)
This checks if the current cell is at the boundary of the grid. The boundary cells are treated differently since they cannot be part of a closed island.
6 : Water Cell Check
if(grid[i][j] == 0)
If the current cell is a water cell (`0`), the Depth First Search (DFS) function is called to mark all connected water cells along the boundary.
7 : DFS Boundary Marking
dfs(grid, i, j, 0, 1);
The DFS function is called to mark all water cells connected to the boundary (changing the water cells to a different value to avoid revisiting).
8 : Closed Island Counter
int cnt = 0;
A counter `cnt` is initialized to keep track of the number of closed islands found in the grid.
9 : Outer Loop (Closed Islands)
for(int i = 0; i < m; i++)
Another outer loop starts to iterate over the rows of the grid to find closed islands.
10 : Inner Loop (Closed Islands)
for(int j = 0; j < n; j++)
An inner loop starts to iterate over the columns of the grid for each row.
11 : Closed Island Detection
if(grid[i][j] == 0) {
If a water cell is found that has not been marked during the boundary DFS, it indicates a closed island. The DFS function is called to mark the whole island.
12 : DFS Closed Island Marking
dfs(grid, i, j, 0, cnt + 2);
The DFS function is called to mark all cells of the current closed island by changing the water cells to a unique value (`cnt + 2`). This also avoids revisiting the same island.
13 : Island Count Increment
cnt++;
The closed island counter `cnt` is incremented after finding and marking the current island.
14 : Return Statement
return cnt;
The function returns the total count of closed islands found in the grid.
15 : DFS Function Definition
void dfs(vector<vector<int>>& grid, int i, int j, int cur, int tgt) {
The helper function `dfs` is defined to traverse and mark connected cells of the grid using Depth First Search. It takes the grid, current position (`i`, `j`), the current value to look for (`cur`), and the target value to mark (`tgt`).
16 : DFS Variable Initialization
int m = grid.size(), n = grid[0].size();
The dimensions of the grid (`m` and `n`) are stored in local variables to simplify the condition checks within the DFS function.
17 : DFS Base Condition
if(i < 0 || j < 0 || i == m || j == n || grid[i][j] != cur)
The base case for the DFS function is defined. If the current cell is out of bounds or does not have the expected value (`cur`), the function terminates the search.
18 : DFS Marking
return;
The DFS function returns if the current cell is out of bounds or not a match for the expected value.
19 : DFS Mark Target
grid[i][j] = tgt;
The current cell is marked with the target value (`tgt`) to indicate it has been visited or processed.
20 : DFS Recursive Calls
dfs(grid, i + 1, j, cur, tgt);
The DFS function is called recursively on the cell below the current one.
21 : DFS Recursive Calls
dfs(grid, i, j + 1, cur, tgt);
The DFS function is called recursively on the cell to the right of the current one.
22 : DFS Recursive Calls
dfs(grid, i - 1, j, cur, tgt);
The DFS function is called recursively on the cell above the current one.
23 : DFS Recursive Calls
dfs(grid, i, j - 1, cur, tgt);
The DFS function is called recursively on the cell to the left of the current one.
Best Case: O(m * n) where m and n are the dimensions of the grid.
Average Case: O(m * n)
Worst Case: O(m * n)
Description: We need to visit every cell in the grid at least once.
Best Case: O(1)
Worst Case: O(m * n)
Description: In the worst case, we may need additional space for DFS recursion stack.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus