grid47 Exploring patterns and algorithms
Oct 18, 2024
7 min read
Solution to LeetCode 200: Number of Islands Problem
You are given a 2D grid representing a map, where ‘1’ represents land and ‘0’ represents water. Your task is to count how many islands are formed by connecting adjacent lands horizontally or vertically. An island is a collection of ‘1’s connected either horizontally or vertically.
Problem
Approach
Steps
Complexity
Input: The input consists of an m x n grid of '1's (land) and '0's (water). The grid is represented as a list of lists where each inner list corresponds to a row in the grid.
• The grid will have between 1 and 300 rows and 1 and 300 columns.
• Each cell of the grid is either '0' or '1'.
Output: Return the number of islands formed in the given grid, where each island consists of connected '1's.
Example: Output: 1
Constraints:
• The output should be an integer representing the number of islands.
Goal: The goal is to count how many distinct islands are present in the grid by connecting adjacent '1's.
Steps:
• Iterate through each cell in the grid.
• When a '1' is encountered, it means the start of a new island. Increment the island count.
• Use Depth First Search (DFS) to mark all connected '1's as visited by changing them to '0'. This ensures that the same island is not counted multiple times.
• Continue until all cells have been processed.
Goal: The grid will always contain at least one row and one column, and each element in the grid is either '0' or '1'.
Steps:
• 1 <= m, n <= 300
• grid[i][j] is either '0' or '1'.
Assumptions:
• The grid is well-formed, with each row containing the same number of columns.
• Explanation: In this example, there are three distinct islands. The first island consists of the first two rows of '1's, the second island is formed by the '1' at position (2,2), and the third island is the '1' at position (3,3). The output is 3.
• Explanation: This grid forms a single island that spans multiple rows and columns. The entire set of '1's is connected horizontally and vertically. The output is 1.
Approach: To solve this problem, we can use Depth First Search (DFS) to explore the grid and mark all cells that belong to the same island. Each time we encounter a '1', we initiate a DFS to mark all the connected '1's as visited.
Observations:
• DFS is an effective way to explore the grid and mark visited nodes. We can treat each '1' as the start of an island and use DFS to find all connected land cells.
• DFS allows us to efficiently mark connected components, and once we've visited all parts of an island, we can proceed to the next unvisited land.
Steps:
• Initialize a counter for the number of islands.
• Iterate through each cell in the grid.
• If the current cell is '1', increment the island count and perform DFS to mark all connected '1's as visited.
• DFS will explore the grid by checking all adjacent cells (up, down, left, right). Mark each visited '1' as '0' to avoid revisiting.
• Return the island count after processing all cells.
Empty Inputs:
• If the grid is empty (m = 0 or n = 0), return 0.
Large Inputs:
• For large grids (e.g., 300 x 300), the solution should efficiently handle the large size without running into time or space issues.
Special Values:
• Handle grids with no land ('1') or only land ('1'). In these cases, the output should be 0 or 1 respectively.
Constraints:
• Ensure that the DFS does not go out of bounds and handles edge cases like single-cell islands or fully connected grids.
intnumIslands(vector<vector<char>>& grid) {
int cnt =0;
int m = grid.size(), n = grid[0].size();
for(int i =0; i < m; i++)
for(int j =0; j < n; j++)
if(grid[i][j] =='1') {
cnt++;
dfs(grid, i, j);
}
return cnt;
}
voiddfs(vector<vector<char>>&grid, int i, int j) {
if(i <0|| j <0|| i == grid.size() || j == grid[0].size() || grid[i][j] =='0')
return ;
grid[i][j] ='0';
dfs(grid, i +1, j);
dfs(grid, i, j +1);
dfs(grid, i -1, j);
dfs(grid, i, j -1);
}
1 : Function Definition
intnumIslands(vector<vector<char>>& grid) {
Define the function 'numIslands' which takes a 2D grid of characters (representing water and land) and returns the number of islands. An island is surrounded by water and is formed by connecting adjacent land cells.
2 : Variable Initialization
int cnt =0;
Initialize a counter 'cnt' to keep track of the number of islands found during the iteration through the grid.
3 : Grid Dimensions
int m = grid.size(), n = grid[0].size();
Store the number of rows (m) and columns (n) of the grid to control the iteration bounds.
4 : Outer Loop
for(int i =0; i < m; i++)
Start the outer loop to iterate through each row of the grid.
5 : Inner Loop
for(int j =0; j < n; j++)
Start the inner loop to iterate through each column of the current row.
6 : Island Detection
if(grid[i][j] =='1') {
Check if the current cell is land ('1'). If it is, it signifies the start of a new island.
7 : Increment Island Count
cnt++;
Increment the island count (cnt) when a new island is found.
8 : DFS Call
dfs(grid, i, j);
Call the DFS function to mark all the connected land cells as visited, ensuring we don't count the same island multiple times.
9 : End of If Statement
}
End the if statement that checks for a land cell.
10 : Return Island Count
return cnt;
Return the total count of islands found after iterating through the entire grid.
11 : DFS Function Definition
voiddfs(vector<vector<char>>&grid, int i, int j) {
Define the helper DFS function that will mark all connected land cells as visited by changing their value to '0'. This helps prevent counting the same island multiple times.
Check if the current position is out of bounds or if the cell is already visited (i.e., it is water or already marked as visited). If any of these conditions is true, stop the DFS.
13 : End DFS if Base Case
return ;
End the DFS function if the base case conditions are met.
14 : Mark Visited Cell
grid[i][j] ='0';
Mark the current cell as visited by changing its value from '1' (land) to '0' (water).
15 : DFS Recursive Calls
dfs(grid, i +1, j);
Recursively call DFS for the neighboring cell below the current cell (downward).
16 : DFS Recursive Call
dfs(grid, i, j +1);
Recursively call DFS for the neighboring cell to the right of the current cell (rightward).
17 : DFS Recursive Call
dfs(grid, i -1, j);
Recursively call DFS for the neighboring cell above the current cell (upward).
18 : DFS Recursive Call
dfs(grid, i, j -1);
Recursively call DFS for the neighboring cell to the left of the current cell (leftward).
Best Case: O(m * n)
Average Case: O(m * n)
Worst Case: O(m * n)
Description: In the worst case, we need to visit every cell in the grid, making the time complexity O(m * n), where m is the number of rows and n is the number of columns.
Best Case: O(1)
Worst Case: O(m * n)
Description: In the worst case, the DFS stack may hold all the cells in the grid, leading to a space complexity of O(m * n). For the best case (a single island), the space complexity is O(1).
