Complexity Analysis
def num_islands(grid):
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
count = 0
def dfs(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != '1':
return
grid[r][c] = '0'
dfs(r+1, c); dfs(r-1, c); dfs(r, c+1); dfs(r, c-1)
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1':
count += 1
dfs(r, c)
return countWhat is the time and space complexity?
Work it out before scrolling down.
Time
O(m × n)
Space
O(m × n)
How to derive it
Every cell is visited at most twice: once by the outer loop, once by DFS (which marks it '0'). Total work: O(m × n). Space: DFS recursion depth can reach m × n in the worst case (a single snake-shaped island filling the grid). The grid modification avoids needing a separate visited set.