200. Number of Islands

Basic steps

• Traverse through each row and column in the grid
• If the position is land and not already visited, traverse it with BFS, and add 1 to the islands count

BFS

A queue (deque) will be used.

• Add the provided coordinate (row, col) to the queue
• While the queue is not empty:
  • Pop the left row and col in the queue
  • For each neighbor of row and col, check if they are land and not already visited
    • If so, add them to the queue and the visited set

import collections 

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        # No islands in empty grid
        if not grid:
            return 0
        
        rows, cols = len(grid), len(grid[0])
        visited = set()
        islands = 0

        def bfs(r, c):
            # Normally queue used for BFS, it is iterative
            q = collections.deque()
            visited.add((r, c))
            q.append((r, c))

            # While queue not empty (there are neighbours), expand island
            while q:
                row, col = q.popleft()
                # Check adjacent position (4 directions)
                directions = [[1,0], [-1,0], [0,1], [0,-1]]
                for dr, dc in directions:
                    # Neighbouring row and column
                    nr, nd = row+dr, col+dc
                    # Ensure in bounds and that position is land
                    if (nr in range(rows) and (nd in range(cols)) and
                       grid[nr][nd] == "1" and (nr, nd) not in visited):
                       # Add to queue because we have to run BFS on this cell
                        q.append((nr, nd))
                        # Mark as visited so we do not visit it twice
                        visited.add((nr, nd))


        # Visit every single position
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == "1" and (r, c) not in visited:
                    # Traverse and mark as visited
                    bfs(r, c)
                    islands += 1
        
        return islands