Q80: Number of Islands. - DSA Patterns (Multi-Lang)

In Simple Words: Iterate through the 2D grid. When a land cell '1' is found, increment island count and trigger BFS/DFS to sink all connected land cells by flipping them to '0'.

Time: $O(M \cdot N)$ | Space: $O(M \cdot N)$

Multi-Language SolutionsPython 3 • JavaScript • TypeScript • Java • C++

Switch tabs or choose All

def numIslands(grid: list[list[str]]) -> int:
    if not grid: return 0
    rows, cols = len(grid), len(grid[0])
    islands = 0

    def dfs(r, c):
        if r < 0 or c < 0 or r >= rows or c >= cols or grid[r][c] != "1":
            return
        grid[r][c] = "0"
        dfs(r + 1, c)
        dfs(r - 1, c)
        dfs(r, c + 1)
        dfs(r, c - 1)

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1":
                islands += 1
                dfs(r, c)
    return islands