Problem Statement
Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.
An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 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
Example 2:
Input: grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
DFS: Recursive
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
# ROWS >= COLS >= 1
ROWS, COLS = len(grid), len(grid[0])
islands = 0
# T: O(N x M)
for r in range(ROWS):
for c in range(COLS):
if grid[r][c] == "1":
islands += 1
self.dfs(grid, r, c)
return islands
# T: O(N x M)
# S: O(N x M) ~ stack space when every cell is land
def dfs(self, grid: List[List[str]], ro: int, co: int):
#print(f"({ro},{co}",end=" ")
ROWS, COLS = len(grid), len(grid[0])
if grid[ro][co] == "1":
grid[ro][co] = "2"
# up, right, down, left
for dr, dc in [(-1,0),(0,1),(1,0),(0,-1)]:
r = ro + dr
c = co + dc
if 0 <= r < ROWS and 0 <= c < COLS and grid[r][c] == "1":
self.dfs(grid, r, c)
#print(f"{ro},{co})",end=" ")
Parenthesis Theorem
If we print out the parent vertex on the first line of the DFS function and then print it out again on the last line, a very interesting pattern emerges. According to the Parenthesis Theorem, we see the call stack between balanced sets of parentheses.
grid = [
["1","1","1"],
["1","1","0"],
]
sol = Solution()
sol.numIslands(grid)
# (0,0 (0,1 (0,2 0,2) (1,1 (1,0 1,0) 1,1) 0,1) 0,0)
DFS: Iterative
from collections import deque
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
ROWS, COLS = len(grid), len(grid[0])
stack = deque()
islands = 0
# T: O(N x M)
for r in range(ROWS):
for c in range(COLS):
if grid[r][c] == "1":
islands += 1
self.dfs(grid, r, c)
return islands
def dfs(self, grid: List[List[str]], ro: int, co: int):
ROWS, COLS = len(grid), len(grid[0])
stack = deque([(ro, co)])
# T: O(N x M)
# S: O(N x M)
while stack:
ro, co = stack.pop()
if grid[ro][co] == "1":
grid[ro][co] = "2"
#print(f"({ro},{co}",end=" ")
# up, right, down, left
# Note: Directions added in reverse order
for dr, dc in [(0,-1),(1,0),(0,1),(-1,0)]:
r = ro + dr
c = co + dc
if 0 <= r < ROWS and 0 <= c < COLS and \
grid[r][c] == "1":
stack.append((r,c))
If we add the directions to the LIFO stack in the reverse order, we will visit the cells in the same order as the recursive approach. Note: Since we don’t keep the parent node around after it has been processed, we can’t print out the closing parentheses.
grid = [
["1","1","1"],
["1","1","0"],
]
sol = Solution()
sol.numIslands(grid)
# (0,0 (0,1 (0,2 (1,1 (1,0