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 <= rows, cols <= 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.
Continue the full explanation
You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.
Editor locked
The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.