Number of Islands

mediumFREEGraphsBlind 75

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: grid, a 2D list whose cells are the single-character strings '1' and '0' (the example shows each row as comma-separated values). Return the island count as an integer.

Example

Input

1,1,1,1,0
1,1,0,1,0
1,1,0,0,0
0,0,0,0,0

Output

Reasoning

grid has $4$ rows and $5$ columns; each cell is the character 1 (land) or 0 (water). Writing cell positions as (row, column) from $(0,0)$ , the land cells are: all of row 0 except column 4, then $(1,0), (1,1), (1,3)$ , then $(2,0), (2,1)$ — $9$ land cells in total. Row 3 is all water.
Two land cells belong to the same island when you can walk from one to the other through land, stepping only up, down, left or right.
The left block $(0,0)$ – $(2,1)$ is a solid $3 \times 2$ patch of land, joined to $(0,2)$ and $(0,3)$ along row 0. The cell $(1,3)$ sits directly below $(0,3)$ , so it is joined too, even though water at $(1,2)$ separates it from $(1,1)$ .
Every one of the $9$ land cells is reachable from every other, so there is exactly one island and the answer is 1.
Notice that diagonal contact does not count: a lone 1 touching another only at a corner is its own island. A grid with no 1 at all gives $0$ .

Constraints

1 <= m, n <= 300
grid[i][j] is '0' or '1'

Learn this in

GraphsDSA Study Plan

More from Blind 75

Alien Dictionaryhard Clone Graphmedium Combination Summedium Word Search IIhard Merge K Sorted Listshard

Concept primer

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 \times 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 \times 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.

solution.py

Python 3.13

Test results