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

Watch It Run

Try it yourself: Open TraceLit and step through every line.

---

Built with TraceLit — the visual algorithm tracer for LeetCode practice.

---

▲ 0 ▼ 0

Comments

Post Comment