NumbersOfIsland.py

# Question link - https://leetcode.com/problems/number-of-islands/description/?envType=study-plan-v2&envId=top-interview-150

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

        # Take rows , cols from grid
        rows,cols = len(grid),len(grid[0])
        # For visited , use set
        visited = set()
        islands = 0

        # Function for bfs
        def bfs(r,c):
            # Queue for bfs
            q = collections.deque()
            visited.add((r,c))
            q.append((r,c))

            # Traverse in queue , if not empty
            while q:
                row , col = q.popleft() #this can be converted into DFS , by just q.pop()
                # Directions - right , left , up , down
                directions = [[1,0],[-1,0],[0,1],[0,-1]]

                # Iterate in a direction for adjacents block in grid
                for dr , dc in directions:
                    r , c = row + dr , col + dc
                    # If r and c are in bound in grid
                    if (r in range(rows) and
                        c in range(cols) and 
                        grid[r][c]=="1" and 
                        (r,c) not in visited):
                        q.append((r,c))
                        visited.add((r,c))

        # For traverse in grid
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == "1" and (r,c) not in visited:
                    bfs(r,c)
                    islands += 1

        return islands