Number of Islands

Posted on

You are given a 2D grid where each cell holds either “1” for land or “0” for water. An island is a group of land cells connected horizontally or vertically (not diagonally). Water surrounds every island, and the grid edges also count as boundaries. Count how many separate islands the grid contains.

Example#

For the grid below the answer is 3.

1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1

The top-left block forms one island, the single center cell another, and the bottom-right pair the third.

Brute force note#

There is no meaningful brute force here beyond the traversal itself. You must visit each land cell once and figure out which island it belongs to. The naive worry is re-counting cells, which you avoid by marking cells as visited.

Optimal approach#

Scan every cell. When you hit an unvisited land cell, that is a brand new island, so increment the counter and launch a flood fill (DFS or BFS) that sinks the whole island by marking every connected land cell as water. Because each cell is marked once, the total work is proportional to the grid size.

 1def num_islands(grid):
 2    if not grid:
 3        return 0
 4    rows, cols = len(grid), len(grid[0])
 5    count = 0
 6
 7    def sink(r, c):
 8        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != "1":
 9            return
10        grid[r][c] = "0"
11        sink(r + 1, c)
12        sink(r - 1, c)
13        sink(r, c + 1)
14        sink(r, c - 1)
15
16    for r in range(rows):
17        for c in range(cols):
18            if grid[r][c] == "1":
19                count += 1
20                sink(r, c)
21    return count
22
23
24grid = [
25    ["1", "1", "0", "0", "0"],
26    ["1", "1", "0", "0", "0"],
27    ["0", "0", "1", "0", "0"],
28    ["0", "0", "0", "1", "1"],
29]
30print(num_islands(grid))  # 3

Complexity#

Time is O(rows times cols) since every cell is examined a constant number of times. Space is O(rows times cols) in the worst case for the recursion stack (a grid that is entirely land). Convert to an explicit stack or queue if recursion depth is a concern.

This is a connected-components problem. Reinforce it with the union-find pattern, then continue through the 60-day curriculum.