Interview challenge · medium · grid, bfs, dfs, graph

Number of Islands

The challenge

Given a 2D grid of '1' (land) and '0' (water), count the islands. An island is a group of land cells connected horizontally or vertically, and surrounded by water.

Example

1 1 0 0 0
0 1 0 0 0      ->  3
0 0 1 0 0
0 0 0 1 1

1 1 1 1 0
1 1 0 1 0      ->  1
1 1 0 0 0
0 0 0 0 0

Idea: scan the grid; every time you hit land you have found a new island, so count it and "sink" it: a depth-first flood that turns all of its connected land into water, so it is never counted again. Every cell is visited a constant number of times: time O(rows x cols).

The solution

1# Number of Islands - ayotl.dev
2def islands(rows):
3    g = [list(r) for r in rows]
4    h, w = len(g), len(g[0])
5
6    def sink(r, c):
7        # flood the island, cell by cell
8        if not (0 <= r < h and 0 <= c < w):
9            return
10        if g[r][c] != "1":
11            return
12        g[r][c] = "0"
13        sink(r + 1, c)
14        sink(r - 1, c)
15        sink(r, c + 1)
16        sink(r, c - 1)
17
18    n = 0
19    for r in range(h):
20        for c in range(w):
21            if g[r][c] == "1":
22                # a new island: sink it
23                n += 1
24                sink(r, c)
25    return n
26
27
28print(islands(["11000", "01000",
29               "00100", "00011"]))
30print(islands(["11110", "11010",
31               "11000", "00000"]))

$ python3 number_of_islands.py

The video

Watch on YouTube →