Number of Islands

GraphsDFSBFS

25 min

Problem Statement

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example

Example 1:

Output: 3

Solution

This is a classic graph traversal problem. We can think of the grid as an adjacency matrix representation of a graph where each '1' is a node and adjacent '1's have an edge between them. The goal is to count the number of connected components.

We can iterate through each cell of the grid. If a cell contains a '1', we increment our island count and then start a traversal (either Depth-First Search or Breadth-First Search) from that cell to find all connected land cells. To avoid recounting, we "sink" the island by changing the '1's to '0's (or another marker) as we visit them.

Algorithm Steps (DFS)

Initialize `islandCount` to 0.
Iterate through each cell `(r, c)` of the grid.
If `grid[r][c]` is '1':
Increment `islandCount`.
Start a DFS from `(r, c)` to find all parts of the island.
In the DFS, mark the current cell as visited (e.g., change '1' to '0').
Recursively call DFS for all 4 adjacent neighbors (up, down, left, right) if they are valid and are '1'.
Return `islandCount`.

Number of Islands Traversal

Island Count: 0

Progress1 / 1

Ready to start.

Number of Islands (DFS)


class Solution:
    def numIslands(self, grid: list[list[str]]) -> int:
        if not grid:
            return 0
        
        rows, cols = len(grid), len(grid[0])
        island_count = 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' # Mark as visited
            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':
                    island_count += 1
                    dfs(r, c)
        
        return island_count