[link](https://leetcode.com/problems/number-of-islands/)

---

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"]
]
Output: 3

#### Constraints:

- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 300
- grid[i][j] is '0' or '1'.

---

The initial check if not grid: ensures that the grid is not empty. If it is empty, the function returns. The visited set is used to keep track of visited cells to avoid processing them multiple times. The islands variable is initialized to 0, which will store the count of islands found.

The dfs function is a helper function that performs a depth-first search on the grid starting from a given cell (r, c). It checks the conditions to determine if the current cell is part of an island, marks it as visited, and recursively calls dfs on its adjacent cells. Inside the dfs function, the dimensions of the grid are determined using ROWS = len(grid) and COLS = len(grid[0]).

The conditions to terminate the DFS recursion are as follows:

If the current cell is out of bounds. If the current cell has been visited before. If the current cell contains '0', indicating it is not part of an island. If the current cell satisfies the above conditions, the function simply returns. If the current cell is a valid part of an island, it is marked as visited by adding (r, c) to the visited set. The DFS recursion continues by calling dfs on the adjacent cells: (r + 1, c), (r - 1, c), (r, c + 1), and (r, c - 1).

After the dfs function, a nested loop is used to iterate over each cell in the grid. If the current cell has not been visited and contains '1', it means a new island has been found. The dfs function is called starting from this cell, and the islands count is incremented.

#### Solution 1: DFS

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid:
            return

        visited = set()
        islands = 0

        def dfs(grid, r, c):
            ROWS, COLS = len(grid), len(grid[0])
            if (min(r, c) < 0 or 
                r == ROWS or c == COLS or 
                (r, c) in visited or 
                grid[r][c] == '0'):
                return

            visited.add((r, c))
            # Option 2:
            # grid[r][c] = '#'
            # and change the logical condition for grid[r][c] != '1'
            dfs(grid, r + 1, c)
            dfs(grid, r - 1, c)
            dfs(grid, r, c + 1)
            dfs(grid, r, c - 1)

        for r in range(len(grid)):
            for c in range(len(grid[0])):
                if (r, c) not in visited and grid[r][c] == '1':
                    dfs(grid, r, c)
                    islands += 1
        return islands
                    
        

O(T): O(n * m)
O(S): O(n * m)

---

The initial check if not grid: ensures that the grid is not empty. If it is empty, the function returns 0. The dimensions of the grid are obtained using rows = len(grid) and cols = len(grid[0]). A visit set is used to keep track of visited cells to avoid processing them multiple times. The islands variable is initialized to 0, which will store the count of islands found.

The bfs function performs a breadth-first search starting from a given cell (r, c). It initializes a queue q using the collections.deque data structure. The current cell (r, c) is marked as visited by adding it to the visit set, and it is enqueued in the queue q. The BFS loop starts with a while loop that continues until the queue q is empty.

Inside the loop, the leftmost element from the queue is dequeued and assigned to row and col. The directions list represents the possible neighboring cells: down, up, right, and left. For each direction, the new row and column values r and c are calculated based on the current cell's position. If the new cell (r, c) is within the grid bounds, contains '1', and has not been visited before, it is enqueued in the q queue, and marked as visited by adding it to the visit set.

After the bfs function, a nested loop is used to iterate over each cell in the grid. If the current cell has not been visited and contains '1', it means a new island has been found. The bfs function is called starting from this cell, and the islands count is incremented.

#### Solution 2: BFS

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid:
            return 0

        rows, cols = len(grid), len(grid[0])
        visit = set()
        islands = 0


        def bfs(r, c):
            q = collections.deque()
            visit.add((r, c))
            q.append((r, c))
            while q:
                row, col = q.popleft()
                directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
                for dr, dc in directions:
                    r, c = row + dr, col + dc
                    if (r in range(rows) and
                        c in range(cols) and
                        grid[r][c] == '1' and
                        (r, c) not in visit):
                        q.append((r, c))
                        visit.add((r, c))


        for r in range(len(grid)):            
            for c in range(len(grid[0])):
                if (r, c) not in visit and grid[r][c] == "1":
                    bfs(r, c)
                    islands += 1
        
        return islands  

O(T): O(n * m)
O(S): O(n * m)