Number of Islands

Count connected groups of '1's in a 2D grid using BFS/DFS or union-find.

matrix graph bfs dfs connected-components

Write a function `num_islands(grid)` that takes a 2D grid of characters '1' (land) and '0' (water) and returns the number of islands. An island is a group of '1's connected horizontally or vertically (not diagonally) and surrounded by water or grid boundaries. Assume the grid is a list of lists of single-character strings, with at least 1 row and 1 column. Modify the input grid as needed; a deep copy is not required.

Constraints

1 <= len(grid), len(grid[0]) <= 300. The grid contains only '0' and '1'. Time complexity should be O(rows * cols), space complexity O(rows * cols) for recursion or visited tracking.

Example

>>> grid = [
...     ['1','1','0','0','0'],
...     ['1','1','0','0','0'],
...     ['0','0','1','0','0'],
...     ['0','0','0','1','1']
... ]
>>> num_islands(grid)
3

>>> num_islands([['0']])
0

>>> num_islands([['1']])
1

25 points ~30 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think of each '1' as a node in a graph. An island is a connected component.

You can traverse land cells using DFS or BFS, marking visited cells to avoid recounting.

Alternatively, you can modify the grid in place: change visited land to '0' to mark it.

Only move in four directions: up, down, left, right.

Test Results

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