Number of Islands in a Grid
Given an m x n 2D grid of '1's (land) and '0's (water), count the number of islands. An island is a group of adjacent land cells connected horizontally or vertically (not diagonally). Land cells on the grid boundary are not wrapped -- the grid is surrounded by water.
Implement the function with signature num_islands(grid), where grid is a 2D list of the single-character strings '0' and '1'. Return the number of islands as an int.
Constraints:
- $1 \leq m, n \leq 300$
grid[i][j]is'0'or'1'
Example 1:
``` Input: grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ] Output: 1 ```
Example 2:
``` Input: grid = [ ["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"] ] Output: 3 ```
Example
num_islands([["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]) -> 3
The top-left 2x2 block of land forms one island, the single land cell in the middle forms a second, and the two connected cells in the bottom-right form a third -- three connected components in total.
Hints
- This is a connected components problem on a grid graph. Each island is one connected component of
'1'cells. - Use DFS or BFS: when you find an unvisited
'1', flood-fill outward in all four directions to mark the entire island as visited. - You can avoid a separate visited array by overwriting visited
'1'cells with'0'in-place. Each cell is processed at most once, giving $O(m \times n)$ total time.
Worked Solution
How to Think About It: This is a connected components problem on a grid graph. Each land cell is a node, and edges connect horizontally/vertically adjacent land cells. The number of islands is just the number of connected components. Scan the grid, and whenever you hit an unvisited '1', run a flood fill (DFS/BFS) to mark all connected land cells as visited, then increment your island count.
Algorithm:
- Iterate over every cell in the grid.
- When you find a
'1'that has not been visited, increment the island counter. - Flood fill from that cell, marking all reachable
'1'cells as visited (here we overwrite them with'0'in place, avoiding a separate visited array). - Continue scanning.
Note: the judge calls the function named num_islands (snake_case), taking the grid as its single argument and returning an int. The implementation below uses an iterative DFS with an explicit stack to avoid Python recursion-limit issues on large all-land grids.
Code:
```python def num_islands(grid): if not grid or not grid[0]: return 0
m, n = len(grid), len(grid[0]) count = 0
def dfs(i, j): stack = [(i, j)] grid[i][j] = '0' while stack: r, c = stack.pop() for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)): if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == '1': grid[nr][nc] = '0' stack.append((nr, nc))
for i in range(m): for j in range(n): if grid[i][j] == '1': count += 1 dfs(i, j)
return count ```
Walkthrough with Example 2:
``` 1 1 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 1 ```
- Scan hits
(0,0)='1'. Island #1. Flood fills(0,0),(0,1),(1,0),(1,1)-- all set to'0'. - Continue scanning. Next
'1'at(2,2). Island #2. Floods just(2,2). - Next
'1'at(3,3). Island #3. Floods(3,3),(3,4). - Result: 3 islands.
Complexity:
- Time: $O(m \\times n)$ -- each cell is visited a constant number of times.
- Space: $O(m \\times n)$ worst case for the explicit stack (a grid that is all land).
Answer: Count connected components of '1' cells via flood fill. Scan the grid; on each unvisited '1', increment the counter and flood-fill to mark all connected land. Time $O(m \\times n)$.
Intuition
Counting islands is really just counting connected components in a graph, which is one of the most fundamental graph algorithms. The grid is just a convenient representation -- each cell is a node, and adjacency gives you edges. DFS flood-fill is the natural approach because it directly answers the question: starting from a land cell, how far can you reach?
This pattern -- flood-fill to find connected regions -- appears everywhere: image segmentation, cluster detection in spatial data, identifying connected trading venues in a network, or finding contiguous time periods of some market regime. The variant with 8-directional connectivity (including diagonals) reduces the island count because diagonal land cells merge into one component. The choice of 4 vs. 8 connectivity is a modeling decision that depends on your definition of adjacency.