Interview challenge · medium · grid, bfs, dfs, graph
Number of Islands
El reto
El enunciado va en inglés, igual que en el vídeo.
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 0Idea: 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).
La solución
# Number of Islands - ayotl.dev
def islands(rows):
g = [list(r) for r in rows]
h, w = len(g), len(g[0])
def sink(r, c):
# flood the island, cell by cell
if not (0 <= r < h and 0 <= c < w):
return
if g[r][c] != "1":
return
g[r][c] = "0"
sink(r + 1, c)
sink(r - 1, c)
sink(r, c + 1)
sink(r, c - 1)
n = 0
for r in range(h):
for c in range(w):
if g[r][c] == "1":
# a new island: sink it
n += 1
sink(r, c)
return n
print(islands(["11000", "01000",
"00100", "00011"]))
print(islands(["11110", "11010",
"11000", "00000"]))
$ python3 number_of_islands.py
3
1