Difficulty: MediumGraphs

Number of Islands

Problem in Plain English

Given a grid of land and water cells, count how many islands appear. Each island is a group of land cells joined horizontally or vertically.

Problem Statement

Given a rectangular grid of characters "1" (land) and "0" (water), return the number of islands.

Two land cells belong to the same island if a path of land cells joins them using only up, down, left and right moves. Diagonal contact does not connect islands. Treat the grid boundary as surrounded by water.

Constraints

m == grid.length and n == grid[i].length; all rows have the same length.
$1 \le m, n \le 300$ .
Every cell is the character "0" or "1".

Examples

Example 1

Input: grid = [["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]]
Output: 1

Every land cell touches another through shared sides, so the grid holds a single island.

Example 2

Input: grid = [["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]
Output: 3

The top-left four cells form one island. The cell (2, 2) is a second, and (3, 3) with (3, 4) is a third. Although (2, 2) and (3, 3) meet diagonally, no shared side joins them, so the answer is 3.

Example 3

Input: grid = [["0"]]
Output: 0

The smallest allowed grid contains only water. There is no starting land cell, so no traversal begins and the answer is 0.

Example 4

Input: grid = [["1"]]
Output: 1

A single land cell needs no land neighbours to form an island. The scan counts it once and its traversal immediately finishes.

Intuition

Think of each land cell as a graph vertex and each shared side between land cells as an edge. An island is one connected component: all cells reachable from one starting land cell. In Example 1, the nine land cells are reachable from (0, 0), even though some are far away in the row scan. Count a component only when the scan finds unclaimed land, then claim every reachable cell before continuing. A separate visited grid preserves the input; changing land to water uses the input itself as the visited record.

Approaches

BFS With Visited

Solution Details

Reveal BFS With Visited: intuition, complexity, and code

Intuition

Scan for land that has not been visited, then use a queue to explore its entire island breadth first. Mark a cell when adding it to the queue so two neighbours cannot schedule the same cell twice. The counter measures traversal starts, not cells. This approach leaves all input characters and row objects unchanged.

Step-by-Step Logic

Allocate a distinct visited row for each grid row and start islands at 0. Scan cells in row-major order, skipping water and visited land. Example 1 first finds (0, 0).
On fresh land, increment islands, mark the cell visited, and enqueue it. In Example 1 the counter becomes 1 and the queue contains [(0, 0)].
Remove the oldest queued cell. Consider neighbours in down, up, right, left order; reject out-of-bounds, water or visited cells. Mark each accepted cell before enqueueing. From (0, 0), enqueue (1, 0) and (0, 1).
Repeat until the queue is empty. In Example 1, processing (0, 2) discovers (0, 3), then (0, 3) discovers (1, 3). All nine land cells become visited.
Resume the outer scan after the seed. Every remaining land cell of Example 1 is already visited; all other cells are water. The scan starts no further traversal and returns 1. In other inputs, each fresh component repeats this process.

Why It Works

At every queue insertion, the cell is land reachable from the current seed, and marking at insertion ensures it enters the queue at most once. Whenever a reachable land cell is processed, all of its unvisited land neighbours are scheduled; induction along any land path shows that every cell in the seed's island is eventually visited. No other island can enter because the traversal crosses only shared sides of land. Therefore the first scanned cell of each island starts exactly one flood, and all later cells of that island are skipped. The counter is exactly the number of islands.

Dry Run

BFS With Visited: variable states at each step
Event / cell removed	Newly visited cells	Pending queue, oldest first	Visited count	Islands
Seed (0, 0)	(0, 0)	[(0, 0)]	1	0 → 1
Remove (0, 0)	(1, 0), (0, 1)	[(1, 0), (0, 1)]	3	1
Remove (1, 0)	(2, 0), (1, 1)	[(0, 1), (2, 0), (1, 1)]	5	1
Remove (0, 1)	(0, 2)	[(2, 0), (1, 1), (0, 2)]	6	1
Remove (2, 0)	(2, 1)	[(1, 1), (0, 2), (2, 1)]	7	1
Remove (1, 1)	none; neighbours visited or water	[(0, 2), (2, 1)]	7	1
Remove (0, 2)	(0, 3)	[(2, 1), (0, 3)]	8	1
Remove (2, 1)	none	[(0, 3)]	8	1
Remove (0, 3)	(1, 3)	[(1, 3)]	9	1
Remove (1, 3)	none	[]	9	1
Resume scan from (0, 1) through (3, 4)	skip 8 visited land cells and 11 water cells	[]	9	return 1

Complexity Analysis

Time Complexity

O(m \cdot n)

Space Complexity

O(m \cdot n)

Let m and n be the row and column counts. The scan inspects mn cells; each land cell enters the queue once and examines four neighbours, so total time is O(mn). The visited matrix always allocates mn boolean slots with distinct rows. Queue storage is at most O(mn), including coordinate pairs; JavaScript retains dequeued entries until that flood finishes, using a head index instead of a linear-cost shift. Java ArrayDeque and Python deque remove from the front efficiently. No copy of the input is made by this approach.

Code

Solution.java

1import java.util.ArrayDeque;2
3class Solution {4    public int numIslands(char[][] grid) {5        int rows = grid.length, cols = grid[0].length;6        boolean[][] visited = new boolean[rows][cols];7        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};8        int islands = 0;9        for (int r = 0; r < rows; r++) {10            for (int c = 0; c < cols; c++) {11                if (grid[r][c] != '1' || visited[r][c]) continue;12                islands++;13                ArrayDeque<int[]> queue = new ArrayDeque<>();14                visited[r][c] = true;15                queue.addLast(new int[]{r, c});16                while (!queue.isEmpty()) {17                    int[] cell = queue.removeFirst();18                    for (int[] d : dirs) {19                        int nr = cell[0] + d[0], nc = cell[1] + d[1];20                        if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;21                        if (grid[nr][nc] != '1' || visited[nr][nc]) continue;22                        // Claim on insertion: multiple neighbours cannot queue this cell twice.23                        visited[nr][nc] = true;24                        queue.addLast(new int[]{nr, nc});25                    }26                }27            }28        }29        return islands;30    }31}

Hints

Hint 1

Model land cells joined by shared sides as one graph component. Does the count depend on how many cells that component contains?

Hint 2

During the row scan, start a traversal only at land that no previous traversal has claimed.

Hint 3

Use a queue or explicit stack to claim the entire component. Mark a cell before scheduling it; choose a visited matrix to preserve the grid or sink cells if mutation is acceptable.

Edge Cases

An all-water grid, including [["0"]], returns 0 without a traversal.
An all-land grid, including the 300 by 300 maximum, returns 1. An explicit traversal avoids recursive stack overflow.
A checkerboard of alternating land and water has one island per land cell; diagonal neighbours remain separate. A 300 by 300 checkerboard has 45000 islands.
A single row or column can contain multiple separated runs of land; each run is one island.
Islands may touch any border. Out-of-bounds positions are skipped, not accessed or counted.
The visited approach can be called again on the same unchanged grid. After sink DFS, every cell is water, so a second call on that same object returns 0. Preserve an original copy if both approaches must run on the same input.

Common Mistakes and Interview Tips

Counting each land cell instead of each fresh traversal start; the nine land cells in Example 1 form only one island.
Using eight directions merges diagonally touching islands that must remain separate.
Marking after removing a queue or stack entry allows converging paths to insert duplicates. Mark when scheduling.
Using recursive DFS without considering the maximum grid size; long connected regions exceed common Python, Java and JavaScript call-stack limits.
Calling JavaScript Array.shift repeatedly can add linear work per removal. Use a head index to keep total queue work linear.
Creating visited rows by repeating one mutable row makes unrelated positions share flags. Allocate independent rows.
Calling sinking constant-space ignores the explicit stack. Explain input mutation and traversal storage separately in an interview; cloning only the outer grid array does not protect shared inner rows.

Key Takeaway

To count connected components, scan for unclaimed vertices, start one traversal per fresh vertex, and mark every reachable vertex before continuing. Grid side-adjacency supplies the graph edges. A visited structure preserves the map; mutation can replace those marks but does not remove traversal memory.