Number of Islands

Given a 2D grid grid where '1' represents land and '0' represents water, count and return the number of islands.

An island is formed by connecting adjacent lands horizontally or vertically and is surrounded by water. You may assume water is surrounding the grid (i.e., all the edges are water).

Approach

Scan the grid and start a DFS/BFS whenever an unvisited land cell ('1') is found. The search marks all connected land cells as visited by sinking them to '0'. Each DFS corresponds to one island.

Why It Works

All cells in an island are connected via horizontal/vertical moves. Starting a search at one land cell marks exactly the entire connected component. Counting how many times we start a search gives the number of islands.

Complexity

• Time: O(m * n)
• Space: O(m * n) in the worst case for recursion/queue

Reference Implementation (Python)

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(r: int, c: int) -> None:
            if r < 0 or c < 0 or r >= rows or c >= cols:
                return
            if grid[r][c] != '1':
                return
            grid[r][c] = '0'
            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':
                    count += 1
                    dfs(r, c)
        return count