Задача с собеседования в Zenefits

Дана двумерная бинарная матрица grid размером m x n, которая представляет карту из единиц (суша) и нулей (вода). Верните количество островов.
Остров окружён водой и сформирован путём соединения соседних участков суши (ячеек "1") по горизонтали или вертикали. Можете считать, что все четыре края сетки окружены водой.

Пример 1:
Input: grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
Output: 1

Пример 2:
Input: grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
Output: 3

Ограничения:
m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] is '0' or '1'.

НАШ ЧАТ АЛГОРИТМИСТОВ

Решение
Задачу можно решить рекурсивным обходом графа в глубину (dfs), так как ограничения размера 300×300 позволяют полагать, что опасности переполнения стека нет.
Вершины графа - ячейки с "1".
Рёбра - соседние ячейки по горизонтали и вертикали.
В цикле проходим по каждой ячейке матрицы, если ячейка содержит "1": увеличиваем количество островов и запускаем рекурсивную функцию dfs. В ней проверяем ячейку на соблюдение границ и помечаем этот участок суши, как пройденный (grid[i][j] = "0"). Следующими вызовами проверяем её соседей по горизонтали и вертикали.
На больших данных оптимальным будет решение через bfs или итеративный dfs, но без условия оптимизации рекурсивное dfs-решение стандартно для этой задачи.

Сложность
O(m*n) - по времени
O(m*n) - по памяти

Код
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
m, n = len(grid), len(grid[0])
num_islands = 0

def dfs(i, j):
if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] != "1":
return
else:
grid[i][j] = "0"
dfs(i, j+1)
dfs(i+1, j)
dfs(i, j-1)
dfs(i-1, j)

for i in range(m):
for j in range(n):
if grid[i][j] == "1":
num_islands += 1
dfs(i, j)

return num_islands

@algoses