Number of Islands
Given a 2D grid of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and formed by connecting adjacent land cells horizontally/vertically.
Input: rows of comma-separated 1/0.
Example:
1,1,1,1,0 1,1,0,1,0 1,1,0,0,0 0,0,0,0,0
1
- The input is a 2D grid of '1's (land) and '0's (water), which can be visualized as:
1 1 1 1 0 1 1 0 1 0 1 1 0 0 0 0 0 0 0 0
* We identify the connected land cells (horizontally/vertically) to form islands. In this case, all the '1's are connected, forming a single large island.
* The number of islands is counted, which in this case is $1$ since all the land cells are part of the same island.
* The final output is the total count of islands, which is $\boxed{1}$.
Constraints:
- 1 <= m, n <= 300
- grid[i][j] is '0' or '1'
Background Knowledge
The "Number of Islands" problem is a classic example of a graph traversal problem, where we need to explore a 2D grid and identify distinct groups of connected land cells. To solve this problem, we need to understand the concept of adjacency, where two cells are considered adjacent if they share a common edge (horizontally or vertically). We also need to understand the concept of connected components, which refers to a group of cells that are connected to each other through adjacency.
In the context of graph theory, an island can be represented as a subgraph, where each land cell is a node, and two nodes are connected by an edge if the corresponding cells are adjacent. The goal is to count the number of disjoint subgraphs, each representing an island. To achieve this, we can use various graph traversal algorithms, such as depth-first search (DFS) or breadth-first search (BFS), to explore the grid and identify the connected components.
The problem also involves image processing concepts, where the 2D grid can be viewed as a binary image, with '1's representing land pixels and '0's representing water pixels. In this context, the problem is equivalent to finding the number of connected regions in the image. Understanding these concepts will help us develop an effective approach to solving the problem.
Algorithm/Approach
The general approach to solving this problem involves using a graph traversal algorithm to explore the 2D grid and identify the connected components. We can use either DFS or BFS to traverse the grid, starting from each unvisited land cell and marking all adjacent land cells as visited. By repeating this process, we can identify all the distinct islands in the grid.
Step-by-Step Strategy
To implement the solution, we can follow these steps:
- Initialize a 2D array to store the visited status of each cell
- Iterate through each cell in the grid
- If a cell is a land cell and has not been visited, perform a DFS or BFS traversal starting from that cell
- Mark all adjacent land cells as visited during the traversal
- Increment the island count each time a new unvisited land cell is encountered
Common Pitfalls
When implementing the solution, we need to watch out for the following:
- Failing to mark visited cells correctly, leading to incorrect island counts
- Not handling edge cases, such as an empty grid or a grid with no land cells
- Using an inefficient traversal algorithm, leading to poor performance for large grids
Time & Space Complexity
The expected time complexity for this problem is O(rows×cols), where rows and cols are the dimensions of the 2D grid, since we need to visit each cell at least once. The expected space complexity is also O(rows×cols), since we need to store the visited status of each cell. However, the actual space complexity can be reduced by using an iterative approach instead of a recursive one.