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