Generated by Codex with GPT-5

Quick facts

• Difficulty: MEDIUM
• Problem: Number of Islands
• Main tags: Array, Depth-First Search, Breadth-First Search, Union-Find, Matrix

What the problem is really asking

The grid is a map of water and land:

• "1" means land
• "0" means water

An island is one connected piece of land using only the four cardinal directions: up, down, left, and right.

So the real task is not “count how many 1s there are.” It is:

how many separate connected land components exist in the grid?

That wording matters, because once one land cell is found, the algorithm has to discover every other land cell that belongs to the same component before counting the next island.

Why the brute-force idea is incomplete

The obvious first thought is to scan the whole grid and increment a counter whenever a land cell appears.

That fails because many land cells belong to the same island. For example, a 2 x 2 block of land is still just one island, not four.

So a plain scan is only half the solution. The other half is:

• detect a new island
• fully traverse that island
• mark every cell in it as already processed

Once that pattern is clear, the problem becomes a standard graph traversal on a matrix.

The key insight

Every land cell belongs to exactly one island.

That means the first time the scan encounters an unvisited land cell, that cell must be the start of a brand-new island. The algorithm can safely:

1. increment the island count
2. run a traversal from that cell
3. mark every reachable land cell so none of them are counted again

This is just flood fill.

The traversal can be done with either:

• DFS
• BFS

Both are optimal here because any correct solution has to inspect the grid cells, and any traversal only visits each land cell a constant number of times.

How to derive the optimal solution

A clean interview derivation is:

1. Scan the grid row by row.
2. When a water cell appears, ignore it.
3. When an unvisited land cell appears, that must start a new island.
4. Expand from it in four directions to consume the whole island.
5. Continue the scan until the grid is exhausted.

The only remaining design question is how to remember which land cells were already consumed.

There are two common choices:

• Keep a separate visited set.
• Mutate the grid in place by turning visited land into water.

For the standard LeetCode version, mutating in place is usually the better final answer because it avoids extra memory and keeps the code simple.

Best solution choices

There are two equally good high-level traversal strategies for this problem:

• Iterative DFS or BFS with in-place marking: O(rows * cols) time and O(rows * cols) worst-case traversal storage, although usually much less in practice.
• Recursive DFS: same asymptotic complexity, but less robust in Python because large islands can hit recursion-depth limits.

There is also a union-find solution, but it is usually not the best first answer for this exact problem. It is more useful when the problem changes into a dynamic connectivity variant.

For production-style Python, iterative traversal is the safest answer.

A simple mental model

Think of the algorithm as:

• walk through the map
• whenever fresh land is found, count one island
• erase that entire island immediately

After an island is erased, no cell from it can accidentally trigger a second count later.

That is why the counting logic stays correct even though the outer loop is just a plain grid scan.

Python solution

from collections import deque
from typing import Deque, List, Tuple


Grid = List[List[str]]
Cell = Tuple[int, int]


class IslandCounter:
    """Count connected components of land in a 2D grid."""

    LAND = "1"
    WATER = "0"
    DIRECTIONS: Tuple[Cell, ...] = ((1, 0), (-1, 0), (0, 1), (0, -1))

    def count_islands(self, grid: Grid) -> int:
        if not grid or not grid[0]:
            return 0

        island_count = 0

        for row_index in range(len(grid)):
            for column_index in range(len(grid[0])):
                if grid[row_index][column_index] != self.LAND:
                    continue

                island_count += 1
                self._sink_island(
                    grid=grid,
                    start_row=row_index,
                    start_column=column_index,
                )

        return island_count

    def _sink_island(self, grid: Grid, start_row: int, start_column: int) -> None:
        """
        Traverse one full island and mark every visited land cell as water.

        A queue is used here instead of recursion so the implementation remains
        safe on large inputs without depending on Python's recursion limit.
        """
        pending_cells: Deque[Cell] = deque([(start_row, start_column)])
        grid[start_row][start_column] = self.WATER

        while pending_cells:
            row_index, column_index = pending_cells.popleft()

            for neighbor_row, neighbor_column in self._land_neighbors(
                grid=grid,
                row_index=row_index,
                column_index=column_index,
            ):
                grid[neighbor_row][neighbor_column] = self.WATER
                pending_cells.append((neighbor_row, neighbor_column))

    def _land_neighbors(
        self,
        grid: Grid,
        row_index: int,
        column_index: int,
    ) -> List[Cell]:
        """Return the adjacent cells that still contain unvisited land."""
        neighbors: List[Cell] = []
        row_count = len(grid)
        column_count = len(grid[0])

        for row_delta, column_delta in self.DIRECTIONS:
            next_row = row_index + row_delta
            next_column = column_index + column_delta

            if not (0 <= next_row < row_count and 0 <= next_column < column_count):
                continue

            if grid[next_row][next_column] != self.LAND:
                continue

            neighbors.append((next_row, next_column))

        return neighbors


class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        island_counter = IslandCounter()
        return island_counter.count_islands(grid)

Why this works

The outer scan guarantees that every cell is considered at least once.

Whenever the scan finds a land cell, that cell cannot belong to any previously counted island, because earlier traversals would already have turned it into water. So each such discovery correctly represents one new island.

The flood fill then visits every land cell connected to that starting cell and marks those cells as processed. That ensures:

• every island contributes exactly one count
• no island is missed
• no island is counted twice

The runtime is O(rows * cols) because each cell is inspected a constant number of times. The extra traversal storage is O(rows * cols) in the worst case when one huge island fills the grid.

Interview follow-ups

What changes if diagonal neighbors also count as connected?

Only the neighborhood definition changes. Instead of exploring four directions, the traversal would explore eight directions by adding the four diagonals. The rest of the algorithm stays exactly the same: scan for fresh land, count a new island, and flood fill to consume the whole component. The complexity is still O(rows * cols) time because each cell is still processed a constant number of times. The main tradeoff is conceptual rather than performance-related: the interviewer is testing whether the candidate encoded adjacency rules clearly instead of hard-coding assumptions into the traversal.

What if the interviewer forbids mutating the input grid?

Then the traversal should keep a separate visited structure, usually a boolean matrix or a set of visited coordinates. The scan still identifies new islands the same way, but instead of turning land into water, the algorithm marks coordinates as visited. This preserves the original input at the cost of extra memory. With a boolean matrix, the complexity remains O(rows * cols) time and O(rows * cols) extra space. That is a good trade when input immutability matters more than minimizing auxiliary storage.

How would union-find fit this problem?

Union-find treats every land cell as a node and unions neighboring land cells into shared components. After processing the grid, the number of distinct roots among land cells is the island count. This also runs in near-linear time and is fully correct, but it is more machinery than necessary for the static version of the problem. Its real advantage appears when connectivity changes over time, such as when land cells are added incrementally and the island count must be updated after each addition. For the standard one-shot LeetCode question, DFS or BFS is easier to explain, easier to implement, and usually the better interview answer.

What if the interviewer asks for the size of each island instead of just the count?

The flood fill can accumulate a current_island_size counter while traversing one connected component. Each time a land cell is removed from the queue, the algorithm increments that size. After the traversal finishes, it stores the completed size in a result list before continuing the outer scan. The traversal complexity stays O(rows * cols) because the same cells are still visited once. The only real difference is in the output: instead of one global counter, the algorithm keeps one measurement per connected component.

Practical takeaway

This problem becomes much easier once it is recognized as connected-component counting on a grid.

The winning pattern is simple:

find fresh land, count one island, flood fill it away.

That is the whole solution, and it is why DFS or BFS is the right default answer.