LeetCode 200 - Number of Islands

Difficulty: 🟡 Medium
Topics: Array, Depth-First Search, Breadth-First Search, Union-Find, Matrix

Solution

Problem Understanding

The problem gives us a two dimensional grid where each cell contains either '1' or '0'.

A cell containing '1' represents land, while a cell containing '0' represents water. An island is defined as a group of connected land cells. Two land cells belong to the same island only if they are connected horizontally or vertically. Diagonal connections do not count.

Our goal is to count how many separate islands exist in the grid.

For example, consider this grid:

1 1 0
0 1 0
1 0 1

The top-left group of connected land cells forms one island. The isolated land cell at the bottom-left forms another island. The bottom-right land cell forms a third island. The answer would therefore be 3.

The constraints tell us that both dimensions of the grid can be as large as 300 x 300. This means the grid may contain up to 90,000 cells. Because of this size, we need an algorithm that efficiently processes every cell. Solutions with extremely high complexity would not be practical.

Several important observations come from the problem statement:

The grid is guaranteed to contain only '0' and '1'
All four edges are surrounded by water conceptually, so we do not need special edge wrapping logic
Connections are only horizontal and vertical
Every land cell belongs to exactly one island

There are also several edge cases that can cause mistakes in naive implementations:

A grid containing only water should return 0
A grid containing only land should return 1
Single-cell grids must be handled correctly
Diagonal land cells must not be treated as connected
Large connected islands may cause repeated traversal if visited cells are not tracked properly

The core challenge is determining which land cells belong to the same connected component.

Approaches

Brute Force Approach

A naive approach would attempt to compare every land cell with every other land cell to determine whether they belong to the same island.

For each '1' cell, we could search outward repeatedly and maintain groups manually. However, without an efficient traversal strategy, the algorithm may revisit the same cells many times. In the worst case, this can lead to excessive repeated work.

For example, imagine a grid full of land. Every new cell might trigger another large search across already explored regions. This causes unnecessary computation and poor scalability.

While this brute-force style approach can eventually produce the correct answer, it becomes inefficient for large grids near the constraint limit.

Optimal Approach, Graph Traversal

The key insight is that the grid naturally forms a graph.

Each land cell is a node, and edges exist between horizontally or vertically adjacent land cells. An island is simply a connected component in this graph.

This means we can solve the problem using either:

Depth-First Search, DFS
Breadth-First Search, BFS

The idea is straightforward:

Iterate through every cell in the grid.
When an unvisited land cell is found, we have discovered a new island.
Start a DFS or BFS traversal from that cell.
Mark every connected land cell as visited.
Continue scanning the grid.

Each island is counted exactly once because after traversal, all cells belonging to that island are marked visited.

This approach is efficient because every cell is processed at most once.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O((m × n)²)	O(m × n)	Repeatedly revisits regions and performs redundant searches
Optimal DFS/BFS	O(m × n)	O(m × n)	Visits each cell once while exploring connected components

Algorithm Walkthrough

DFS Traversal Strategy

We will use Depth-First Search for the implementation.

Start by determining the number of rows and columns in the grid. These dimensions are needed for boundary checks during traversal.
Create a variable called island_count initialized to 0. This variable tracks how many distinct islands have been discovered.
Traverse every cell in the grid using nested loops.
For each cell, check whether it contains land ('1').
If the cell contains water ('0'), skip it because water cannot belong to an island.
If the cell contains land, we have discovered a new island. Increment island_count.
Start a DFS traversal from this cell. The purpose of DFS is to visit every land cell connected to the current island.
Inside DFS:

Mark the current cell as visited
Explore all four directions:
up
down
left
right

For each neighboring cell:

Ensure the coordinates remain inside grid boundaries
Continue DFS only if the neighbor is also land

To avoid revisiting cells repeatedly, mark visited land cells as water ('0'). This modifies the grid directly and removes the need for a separate visited matrix.
Once DFS finishes, the entire island has been processed.
Continue scanning the remaining cells in the grid until every position has been checked.

At the end, island_count contains the total number of islands.

Python Solution

from typing import List

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid or not grid[0]:
            return 0

        rows = len(grid)
        cols = len(grid[0])

        def dfs(row: int, col: int) -> None:
            if (
                row < 0
                or row >= rows
                or col < 0
                or col >= cols
                or grid[row][col] == "0"
            ):
                return

            grid[row][col] = "0"

            dfs(row - 1, col)
            dfs(row + 1, col)
            dfs(row, col - 1)
            dfs(row, col + 1)

        island_count = 0

        for row in range(rows):
            for col in range(cols):
                if grid[row][col] == "1":
                    island_count += 1
                    dfs(row, col)

        return island_count

The implementation begins with a safety check for empty input. Although the constraints guarantee valid dimensions, defensive programming makes the solution more robust.

The nested dfs function performs the recursive traversal. The first condition checks whether the coordinates are outside the grid or whether the current cell is water. If any of these conditions are true, recursion stops immediately.

When a land cell is visited, it is changed from '1' to '0'. This serves as the visited marker. Because of this modification, future traversals will not process the same cell again.

The DFS then recursively explores all four neighboring directions.

The outer nested loops scan the entire grid. Every time an unvisited land cell is encountered, a new island has been discovered. The counter increases, and DFS removes the entire connected component from future consideration.

This guarantees that each island contributes exactly one increment to the final answer.

Go Solution

func numIslands(grid [][]byte) int {
    if len(grid) == 0 || len(grid[0]) == 0 {
        return 0
    }

    rows := len(grid)
    cols := len(grid[0])

    var dfs func(int, int)

    dfs = func(row int, col int) {
        if row < 0 || row >= rows || col < 0 || col >= cols || grid[row][col] == '0' {
            return
        }

        grid[row][col] = '0'

        dfs(row-1, col)
        dfs(row+1, col)
        dfs(row, col-1)
        dfs(row, col+1)
    }

    islandCount := 0

    for row := 0; row < rows; row++ {
        for col := 0; col < cols; col++ {
            if grid[row][col] == '1' {
                islandCount++
                dfs(row, col)
            }
        }
    }

    return islandCount
}

The Go implementation follows the same logic as the Python solution. One notable difference is that Go uses [][]byte instead of List[List[str]].

The recursive DFS function is declared using a function variable because recursive anonymous functions require prior declaration in Go.

Visited cells are still marked directly inside the grid by replacing '1' with '0'. Since Go slices are reference-like structures, modifications inside DFS affect the original grid automatically.

Integer overflow is not a concern because the maximum number of cells is only 90,000.

Worked Examples

Example 1

Input:

[
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]

Initial Grid

Row	Values
0	1 1 1 1 0
1	1 1 0 1 0
2	1 1 0 0 0
3	0 0 0 0 0

Traversal Process

Step	Cell	Action	Island Count
1	(0,0)	Found new island, start DFS	1
2	DFS explores all connected land	Entire region marked visited	1
3	Continue scanning grid	Remaining cells are water or visited	1

Final Grid After DFS

Final answer:

Example 2

Input:

[
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]

Initial Grid

Row	Values
0	1 1 0 0 0
1	1 1 0 0 0
2	0 0 1 0 0
3	0 0 0 1 1

Traversal Process

Step	Cell	Action	Island Count
1	(0,0)	New island discovered	1
2	DFS marks top-left block	First island complete	1
3	(2,2)	New isolated island	2
4	DFS marks single cell	Second island complete	2
5	(3,3)	New island discovered	3
6	DFS visits (3,4)	Third island complete	3

Final Grid After DFS

Final answer:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m × n)	Every cell is visited at most once
Space	O(m × n)	Recursive DFS stack may contain many cells in worst case

The algorithm scans every grid position exactly once. Although DFS recursively explores neighbors, no cell is revisited after being marked visited. Therefore, the total amount of work is proportional to the number of cells.

The space complexity comes primarily from recursion depth. In the worst case, such as a grid filled entirely with land, the recursion stack may contain up to m × n calls.

Edge Cases

Grid Containing Only Water

Consider this input:

[
  ["0","0"],
  ["0","0"]
]

A buggy implementation might incorrectly increment the island counter or attempt unnecessary traversal.

In this solution, DFS is only triggered when a cell contains '1'. Since no land exists, the counter remains 0.

Grid Containing Only Land

Consider:

[
  ["1","1"],
  ["1","1"]
]

A naive implementation might count each cell separately if visited tracking is missing.

Our DFS traversal marks every connected land cell as visited during the first exploration. As a result, the entire grid becomes processed after one DFS call, producing the correct answer of 1.

Diagonal Connections

Consider:

[
  ["1","0"],
  ["0","1"]
]

These two land cells touch diagonally but are not connected according to the problem rules.

The implementation only explores four directions: up, down, left, and right. Diagonal neighbors are never traversed, so the algorithm correctly counts two separate islands.

Single Cell Grid

Consider:

[
  ["1"]
]

[
  ["0"]
]

Small inputs often expose boundary-checking bugs.

The DFS boundary conditions correctly handle coordinates outside the grid, and the outer traversal works even when the grid contains only one element. Therefore, the implementation correctly returns either 1 or 0 depending on the cell value.