LC 0200 [M] Number of Islands - ALawliet/algorithms GitHub Wiki

same as number of connected components just with a built-in visited check and neighbor list with the grid the DFS in this case "sinks" the islands and marks them visited

if r < 0 or c < 0 or r >= len(grid) or c >= len(grid[0]) or grid[r][c] != '1': return
if 0 <= r < len(grid) and 0 <= c < len(grid[0]) and grid[r][c] == '1': # keep going

DIRS = [(+1,0), (-1,0), (0,-1), (0,+1)]

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        n_rows, n_cols = len(grid), len(grid[0])
        n_connected = 0

        def dfs(r, c):
            # here anything that's not '1' acts as not relevant or visited already
            if 0 <= r < n_rows and 0 <= c < n_cols and grid[r][c] == '1': # inbounds and connected
                grid[r][c] = 0 # sink/mark visited
                for dr, dc in DIRS:
                    nr, nc = r + dr, c + dc
                    dfs(nr, nc)
                      
        for r in range(n_rows):
            for c in range(n_cols):
                if grid[r][c] == '1':
                    n_connected += 1
                    dfs(r, c)

        return n_connected
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        def dfs(r, c):
            # here anything that's not '1' acts as not relevant or visited already
            if 0 <= r < len(grid) and 0 <= c < len(grid[0]) and grid[r][c] == '1':
                grid[r][c] = 0 # sink/mark visited
                dfs(r+1,c) ; dfs(r-1,c) ; dfs(r,c+1) ; dfs(r,c-1)

        num_components = 0
        for r in range(len(grid)):
            for c in range(len(grid[0])):
                if grid[r][c] == '1':
                    num_components += 1
                    dfs(r, c)
        return num_components
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        def dfs(r, c):
            if 0 <= r < len(grid) and 0 <= c < len(grid[0]) and grid[r][c] == '1':
                grid[r][c] = 'v'
                list(map(dfs, 
                         (r+1, r-1, r, r),
                         (c, c, c+1, c-1)
                        ))
                return 1
            return 0
        return sum(dfs(r, c) for r in range(len(grid)) for c in range(len(grid[0])))

footer

⚠️ **GitHub.com Fallback** ⚠️