LeetCode 200: Number Of Islands — Step-by-Step Visual Trace

#python #algorithms #leetcode

Medium — Graph | Depth-First Search | Matrix | Connected Components

The Problem

Given a 2D grid map of '1's (land) and '0's (water), count the number of islands where an island is surrounded by water and formed by connecting adjacent lands horizontally or vertically.

Approach

Use depth-first search (DFS) to explore each unvisited land cell ('1') and mark all connected land cells as visited by changing them to '0'. Each DFS traversal represents one complete island, so increment the island counter for each DFS call initiated from the main loop.

Time: O(m × n) · Space: O(m × n)

Code

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

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

        def dfs(row, col):
            if (
                row < 0
                or row >= rows
                or col < 0
                or col >= cols
                or grid[row][col] == "0"
            ):
                return

            grid[row][col] = "0"  # Mark the cell as visited
            directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

            for dr, dc in directions:
                dfs(row + dr, col + dc)

        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == "1":
                    count += 1
                    dfs(i, j)

        return count