### 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
``````

Leetcode 200 Number of Islands