Number of Islands

PracticeNeetCode ↗LeetCode ↗

Given a 2D grid of "1" (land) and "0" (water), return the number of islands. An island is a group of land cells connected horizontally or vertically, surrounded by water.

Example

Key Pointers

• Every unvisited land cell you encounter is the start of a brand-new island — flood-fill (DFS/BFS) from it to mark every connected land cell.
• Marking cells visited as they're discovered prevents the same island from being counted more than once.
• The answer is just how many times a fresh flood-fill starts, not the size of any individual island.

Step-by-Step Analysis

1. Scan every cell in the grid in order.
2. When an unvisited "1" is found, increment the island count and flood-fill from it.
3. The flood-fill marks every horizontally/vertically connected "1" as visited so it's never re-counted.
4. After scanning the full grid, return the island count.

Complexity

Time: O(rows · cols) — Space: O(rows · cols)

Code

from collections import deque

def numIslands(grid: list[list[str]]) -> int:
    if not grid:
        return 0

    rows, cols = len(grid), len(grid[0])
    visited = set()
    islands = 0

    def bfs(r: int, c: int) -> None:
        queue = deque([(r, c)])
        visited.add((r, c))
        while queue:
            row, col = queue.popleft()
            for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                nr, nc = row + dr, col + dc
                if (0 <= nr < rows and 0 <= nc < cols and
                        grid[nr][nc] == "1" and (nr, nc) not in visited):
                    visited.add((nr, nc))
                    queue.append((nr, nc))

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1" and (r, c) not in visited:
                islands += 1
                bfs(r, c)

    return islands

Code Explanation

How the solution above works, piece by piece.

1. visited remembers land cells already assigned to an island.
2. Scan every cell. Unvisited land means a new island: count it and flood it with bfs.
3. bfs queues the start cell, then repeatedly pops a cell and queues each of its 4 neighbours that is land, inside the grid, and not yet visited.
4. Cells are marked visited when queued, so none is queued twice.
5. Every cell is looked at a constant number of times: O(rows × cols) time and space.

Visual Walkthrough

Running it on the example grid:

Video Explanation

NeetCode — Number of Islands, LeetCode 200