Number of Islands in a Matrix

Count distinct islands in a binary grid using DFS or BFS traversal.

matrix dfs bfs grid islands

You are given a 2D matrix `grid` of size `m x n` where each cell is either `0` (water) or `1` (land). An **island** is a group of connected `1`s, where connectivity is horizontal or vertical (not diagonal). The grid is surrounded by water.

Write a function `num_islands(grid)` that returns the number of distinct islands.

**Function signature:**
```python
def num_islands(grid):
    pass
```

**Input:**
- `grid`: a non-empty list of lists of integers (only 0s and 1s). The inner lists have the same length.

**Output:**
- An integer representing the number of islands.

Constraints

1 <= m, n <= 100
`grid` contains only 0s and 1s.
Time complexity: O(m*n), Space complexity: O(m*n) (visited set) or O(min(m,n)) if you modify the grid in-place (not required).

Example

>>> num_islands([
...   [1,1,0,0,0],
...   [1,1,0,0,0],
...   [0,0,1,0,0],
...   [0,0,0,1,1]
... ])
3
>>> num_islands([
...   [1,0,1],
...   [0,1,0],
...   [1,0,1]
... ])
5

20 points ~20 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

You can iterate over every cell. When you find a '1' that hasn't been visited, increment the count and start a traversal from that cell to mark the whole island as visited.

Use DFS (recursive or stack) or BFS (queue) to explore all 1s adjacent horizontally or vertically.

Be careful not to revisit cells; you can use a visited set or modify the grid in-place by setting visited land cells to 0.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.