Number of Islands
Description
Given an m × n 2D binary grid where each cell is either '1' (land) or '0' (water), count the total number of islands in the grid.
An island is a group of '1' cells that are connected horizontally or vertically (not diagonally). In other words, two land cells belong to the same island if you can walk from one to the other by stepping only up, down, left, or right — never diagonally. Every island is completely surrounded by water (or the boundary of the grid).
You may assume that all four edges of the grid are surrounded by water.
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
Explanation: All the land cells ('1') in the grid are connected to each other horizontally or vertically. Starting from any land cell, you can reach every other land cell by moving up, down, left, or right. Therefore, they all form a single island. The entire bottom row is water, which surrounds the island from below.
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
Explanation: There are three separate groups of connected land cells:
- Island 1: cells (0,0), (0,1), (1,0), (1,1) — a 2×2 block in the top-left
- Island 2: cell (2,2) — a single land cell in the middle, isolated by water on all four sides
- Island 3: cells (3,3), (3,4) — two land cells connected horizontally in the bottom-right
These three groups are separated by water, so they count as three distinct islands.
Example 3
Input: grid = [["0","0","0"],["0","0","0"]]
Output: 0
Explanation: The entire grid is water. There are no land cells at all, so there are zero islands.
Constraints
- m == grid.length
- n == grid[i].length
- 1 ≤ m, n ≤ 300
- grid[i][j] is '0' or '1'
Editorial
Brute Force
Intuition
The most straightforward way to count islands is to scan the grid cell by cell, and whenever we find a land cell ('1') that hasn't been visited yet, we know we've discovered a new island. We then explore all land cells connected to it (its entire island) using Depth-First Search (DFS), marking each cell as visited so we don't count the same island twice.
Think of it like exploring a foggy archipelago from a helicopter. You fly over the ocean in a systematic pattern (row by row). When you spot a patch of land, you increment your island counter, then send a ground team to walk across every connected piece of that island and plant flags (mark visited). Later, when your helicopter flies over flagged land, you skip it — you've already counted that island. When you spot unflagged land, it must be a brand-new island.
To keep the original grid unchanged, we maintain a separate boolean visited matrix of the same dimensions.
Step-by-Step Explanation
Let's trace through the smaller grid from Example 2:
grid = [[1,1,0,0,0],
[1,1,0,0,0],
[0,0,1,0,0],
[0,0,0,1,1]]
Step 1: Initialize a visited matrix of the same size (all false). Set islandCount = 0. Start scanning from (0,0).
Step 2: Cell (0,0) = '1' and not visited. New island found! Increment islandCount = 1. Launch DFS from (0,0).
Step 3: DFS from (0,0): Mark (0,0) visited. Check neighbors: right (0,1) is '1' and unvisited → recurse. Down (1,0) is '1' and unvisited → recurse later.
Step 4: DFS reaches (0,1): Mark visited. Right (0,2) is '0' → skip. Down (1,1) is '1' → recurse.
Step 5: DFS reaches (1,1): Mark visited. Right (1,2) is '0' → skip. Down (2,1) is '0' → skip. Left (1,0) is '1' and unvisited → recurse.
Step 6: DFS reaches (1,0): Mark visited. Down (2,0) is '0' → skip. All neighbors of (1,0) are either visited or water. DFS backtracks. The entire first island {(0,0),(0,1),(1,0),(1,1)} is now fully visited.
Step 7: Continue scanning. Cells (0,2) through (2,1) are all '0' or already visited. Skip them.
Step 8: Cell (2,2) = '1' and not visited. New island found! Increment islandCount = 2. DFS from (2,2): all four neighbors are '0'. Only (2,2) in this island.
Step 9: Continue scanning. Cells (2,3) through (3,2) are '0'. Skip.
Step 10: Cell (3,3) = '1' and not visited. New island found! Increment islandCount = 3. DFS from (3,3): right neighbor (3,4) is '1' → recurse and mark visited. No more unvisited land neighbors.
Step 11: Continue scanning. Cell (3,4) already visited. Scanning complete. Return islandCount = 3.
DFS Island Counting — Scanning and Exploring — Watch how we scan the grid row by row. Each time we find unvisited land, we increment the island count and DFS through the entire island, marking all its cells visited.
Algorithm
- Create a visited matrix of size m × n, initialized to false
- Initialize islandCount = 0
- For each cell (i, j) in the grid (row by row, left to right):
a. If grid[i][j] == '1' and visited[i][j] == false:- Increment islandCount
- Run DFS/BFS from (i, j) to mark all connected land cells as visited
- DFS(i, j):
a. Mark visited[i][j] = true
b. For each of the 4 neighbors (up, down, left, right):- If the neighbor is within bounds, is '1', and is not visited → recurse
- Return islandCount
Code
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int m = grid.size();
int n = grid[0].size();
vector<vector<bool>> visited(m, vector<bool>(n, false));
int islandCount = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '1' && !visited[i][j]) {
islandCount++;
dfs(grid, visited, i, j, m, n);
}
}
}
return islandCount;
}
private:
void dfs(vector<vector<char>>& grid, vector<vector<bool>>& visited,
int r, int c, int m, int n) {
visited[r][c] = true;
int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, -1, 1};
for (int d = 0; d < 4; d++) {
int nr = r + dr[d];
int nc = c + dc[d];
if (nr >= 0 && nr < m && nc >= 0 && nc < n
&& grid[nr][nc] == '1' && !visited[nr][nc]) {
dfs(grid, visited, nr, nc, m, n);
}
}
}
};class Solution:
def numIslands(self, grid: list[list[str]]) -> int:
if not grid:
return 0
m, n = len(grid), len(grid[0])
visited = [[False] * n for _ in range(m)]
island_count = 0
def dfs(r, c):
visited[r][c] = True
for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == '1' and not visited[nr][nc]:
dfs(nr, nc)
for i in range(m):
for j in range(n):
if grid[i][j] == '1' and not visited[i][j]:
island_count += 1
dfs(i, j)
return island_countclass Solution {
public int numIslands(char[][] grid) {
int m = grid.length;
int n = grid[0].length;
boolean[][] visited = new boolean[m][n];
int islandCount = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '1' && !visited[i][j]) {
islandCount++;
dfs(grid, visited, i, j, m, n);
}
}
}
return islandCount;
}
private void dfs(char[][] grid, boolean[][] visited,
int r, int c, int m, int n) {
visited[r][c] = true;
int[] dr = {-1, 1, 0, 0};
int[] dc = {0, 0, -1, 1};
for (int d = 0; d < 4; d++) {
int nr = r + dr[d];
int nc = c + dc[d];
if (nr >= 0 && nr < m && nc >= 0 && nc < n
&& grid[nr][nc] == '1' && !visited[nr][nc]) {
dfs(grid, visited, nr, nc, m, n);
}
}
}
}Complexity Analysis
Time Complexity: O(m × n)
We visit every cell in the grid exactly once during the scanning phase. The DFS also visits each land cell at most once (since we mark them visited). In total, every cell is processed at most twice (once during scanning, once during DFS), giving O(m × n).
Space Complexity: O(m × n)
The visited matrix takes O(m × n) space. Additionally, the DFS recursion stack can go up to O(m × n) deep in the worst case (when the entire grid is land and forms a single spiral-like island).
Why This Approach Is Not Efficient
The DFS approach with a separate visited matrix works correctly and runs in O(m × n) time, which is already optimal since we must examine every cell at least once. However, it has two practical drawbacks:
-
Extra space for the visited matrix: We allocate an entire m × n boolean matrix just to track which cells we've seen. For a 300 × 300 grid, that's 90,000 extra booleans.
-
Deep recursion risk: For large grids where a single island covers most of the grid (e.g., a 300 × 300 grid that is entirely land), the DFS recursion depth can reach 90,000 frames. This can cause a stack overflow in languages with limited stack size.
We can eliminate the visited matrix entirely by modifying the grid in-place — when we visit a land cell, we change it from '1' to '0' (sink the land). This reduces space from O(m × n) to O(m × n) for the recursion stack only. To also avoid the deep recursion problem, we can switch from DFS to BFS, which uses a queue instead of the call stack. BFS's queue will hold at most O(min(m, n)) elements for a well-shaped island, making it more memory-efficient in practice.
Optimal Approach - BFS with In-Place Grid Modification
Intuition
Instead of using a separate visited matrix, we can mark cells as visited by modifying the grid itself — changing '1' to '0' after visiting ("sinking" the land). This eliminates the extra space for the visited matrix.
Instead of recursive DFS (which risks stack overflow on large grids), we use BFS with an explicit queue. BFS explores the island layer by layer from the starting cell outward, like ripples spreading across a pond. Each layer represents cells that are one step farther from the starting cell.
Imagine you discover an island and pour water from the discovery point. The water spreads outward one step at a time — first flooding the immediate neighbors, then their neighbors, and so on. By the time the water stops spreading (no more dry land to reach), the entire island has been submerged.
The algorithm scans the grid cell by cell. When it finds a '1', it increments the island count and launches BFS to sink the entire island. After BFS, all cells of that island are '0', so they won't trigger another island count later.
Step-by-Step Explanation
Let's trace through with the grid from Example 2:
grid = [[1,1,0,0,0],
[1,1,0,0,0],
[0,0,1,0,0],
[0,0,0,1,1]]
Step 1: Initialize islandCount = 0. Start scanning from (0,0).
Step 2: Cell (0,0) = '1'. New island! islandCount = 1. Add (0,0) to BFS queue. Set grid[0][0] = '0' (sink it).
Step 3: BFS dequeues (0,0). Check neighbors: right (0,1) = '1' → enqueue, sink. Down (1,0) = '1' → enqueue, sink. Queue: [(0,1), (1,0)].
Step 4: BFS dequeues (0,1). Check neighbors: right (0,2) = '0' → skip. Down (1,1) = '1' → enqueue, sink. Left (0,0) = '0' (already sunk). Queue: [(1,0), (1,1)].
Step 5: BFS dequeues (1,0). All neighbors are '0' or already sunk. Queue: [(1,1)].
Step 6: BFS dequeues (1,1). All neighbors are '0' or already sunk. Queue empty. Island 1 fully sunk.
Step 7: Continue scanning. Skip water cells until (2,2) = '1'. New island! islandCount = 2. BFS from (2,2): all neighbors are '0'. Island 2 is just one cell. Sink it.
Step 8: Continue scanning. Skip water cells until (3,3) = '1'. New island! islandCount = 3. BFS: enqueue (3,3), sink. Dequeue (3,3), neighbor (3,4) = '1' → enqueue, sink. Dequeue (3,4), all neighbors are '0' or out of bounds. Island 3 sunk.
Step 9: Scanning complete. Return islandCount = 3.
BFS Island Counting — Flood-Fill Sinking — Watch how BFS spreads outward from each discovered land cell, sinking the entire island by turning '1's to '0's. Each new '1' found during scanning starts a new island count.
Algorithm
- Initialize islandCount = 0
- For each cell (i, j) in the grid:
a. If grid[i][j] == '1':- Increment islandCount
- Set grid[i][j] = '0' (sink it)
- Add (i, j) to a BFS queue
- While the queue is not empty:
- Dequeue a cell (r, c)
- For each of the 4 neighbors (nr, nc):
- If within bounds and grid[nr][nc] == '1':
- Set grid[nr][nc] = '0' (sink it)
- Enqueue (nr, nc)
- If within bounds and grid[nr][nc] == '1':
- Return islandCount
Code
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int m = grid.size();
int n = grid[0].size();
int islandCount = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '1') {
islandCount++;
// BFS to sink the entire island
queue<pair<int, int>> q;
grid[i][j] = '0';
q.push({i, j});
while (!q.empty()) {
auto [r, c] = q.front();
q.pop();
int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, -1, 1};
for (int d = 0; d < 4; d++) {
int nr = r + dr[d];
int nc = c + dc[d];
if (nr >= 0 && nr < m && nc >= 0 && nc < n
&& grid[nr][nc] == '1') {
grid[nr][nc] = '0';
q.push({nr, nc});
}
}
}
}
}
}
return islandCount;
}
};from collections import deque
class Solution:
def numIslands(self, grid: list[list[str]]) -> int:
if not grid:
return 0
m, n = len(grid), len(grid[0])
island_count = 0
for i in range(m):
for j in range(n):
if grid[i][j] == '1':
island_count += 1
# BFS to sink the entire island
grid[i][j] = '0'
queue = deque([(i, j)])
while queue:
r, c = queue.popleft()
for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == '1':
grid[nr][nc] = '0'
queue.append((nr, nc))
return island_countclass Solution {
public int numIslands(char[][] grid) {
int m = grid.length;
int n = grid[0].length;
int islandCount = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '1') {
islandCount++;
// BFS to sink the entire island
grid[i][j] = '0';
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{i, j});
int[] dr = {-1, 1, 0, 0};
int[] dc = {0, 0, -1, 1};
while (!queue.isEmpty()) {
int[] cell = queue.poll();
for (int d = 0; d < 4; d++) {
int nr = cell[0] + dr[d];
int nc = cell[1] + dc[d];
if (nr >= 0 && nr < m && nc >= 0 && nc < n
&& grid[nr][nc] == '1') {
grid[nr][nc] = '0';
queue.offer(new int[]{nr, nc});
}
}
}
}
}
}
return islandCount;
}
}Complexity Analysis
Time Complexity: O(m × n)
Every cell is visited at most once during scanning and at most once during BFS. The total work across all BFS calls is proportional to the number of land cells, which is at most m × n. So the overall time is O(m × n).
Space Complexity: O(min(m, n))
The space is dominated by the BFS queue. In the worst case, the queue holds at most O(min(m, n)) cells at once — this happens when a row or column of land forms a wave front. We eliminated the O(m × n) visited matrix by modifying the grid in-place. Note: if the grid cannot be modified, the DFS approach with a visited matrix (O(m × n) space) is the alternative.