200. Number of Islands

Approach: DFS

This is a classic graph problem where we need to count the number of connected components in a 2D grid.

Algorithm:

Initialize a counter for the number of islands.
Iterate through each cell in the grid.
If a cell is part of an island (i.e., it is '1'), increment the counter and perform a depth-first search to mark all connected cells as visited.
Return the counter.

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

        rows, cols = len(grid), len(grid[0])

        def dfs(r, c):
            if r < 0 or c < 0 or r >= rows or c >= cols or grid[r][c] == '0':
                return

            grid[r][c] = '0'

            dfs(r-1, c)
            dfs(r+1, c)
            dfs(r, c-1)
            dfs(r, c+1)

        islands = 0
        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == '1':
                    dfs(i, j)
                    islands += 1

        return islands

Time: $O(m \times n)$ — we visit each cell in the grid at most once.
Space: $O(m \times n)$ — in the worst case, the call stack can go as deep as the number of cells in the grid.

Last updated on

200. Number of Islands

Approach: DFS

On this page