Given an m x n 2D grid of characters where ‘1’ represents land and ‘0’ represents water, return the number of islands. An island is formed by connecting adjacent land cells horizontally or vertically, and is surrounded by water on all sides. You may assume the grid edges are all surrounded by water.
Example
grid = [
["1","1","0","0"],
["1","0","0","1"],
["0","0","1","1"]
]
Output: 2
There are two separate groups of connected land cells. The first island consists of the three 1s in the upper-left corner, and the second island consists of the three 1s in the lower-right area. They are separated by water and not connected horizontally or vertically.
Scan the grid cell by cell. Each time you find a '1', increment your island count and immediately flood-fill (DFS or BFS) to mark all connected '1's as '0' so you don't count them again. The number of times you trigger a flood-fill is the total number of islands.
Why this works
Each island is a connected group of ‘1’ cells. When you find an unvisited ‘1’, you know it is a new island. By flood-filling (DFS) from that cell and turning every connected ‘1’ into ‘0’, you “sink” the entire island so it will not be counted again. The total number of flood-fills you trigger equals the number of islands.
Step by step
- Scan the grid — iterate through every cell row by row.
- Find a ‘1’ — when you hit a land cell, increment the island counter.
- Flood-fill with DFS — from that cell, recursively visit all four neighbors. Mark each visited ‘1’ as ‘0’ to prevent revisiting.
- Continue scanning — after the DFS finishes, the entire island is sunk. Move on to find the next unvisited ‘1’.
Time: O(m×n)
Space: O(m×n)
class Solution {
public int numIslands(char[][] grid) {
int rows = grid.length, cols = grid[0].length;
int count = 0;
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (grid[r][c] == '1') {
count++; // found a new island
dfs(grid, r, c); // sink the entire island
}
}
}
return count;
}
private void dfs(char[][] grid, int r, int c) {
if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length
|| grid[r][c] == '0') {
return; // out of bounds or already water
}
grid[r][c] = '0'; // sink this cell so we don't revisit it
dfs(grid, r + 1, c);
dfs(grid, r - 1, c);
dfs(grid, r, c + 1);
dfs(grid, r, c - 1);
}
}
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int rows = grid.size(), cols = grid[0].size();
int count = 0;
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (grid[r][c] == '1') {
count++; // found a new island
dfs(grid, r, c); // sink the entire island
}
}
}
return count;
}
private:
void dfs(vector<vector<char>>& grid, int r, int c) {
if (r < 0 || r >= grid.size() || c < 0 || c >= grid[0].size()
|| grid[r][c] == '0') {
return; // out of bounds or already water
}
grid[r][c] = '0'; // sink this cell so we don't revisit it
dfs(grid, r + 1, c);
dfs(grid, r - 1, c);
dfs(grid, r, c + 1);
dfs(grid, r, c - 1);
}
};
def numIslands(grid: list[list[str]]) -> int:
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
count = 0
def dfs(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == '0':
return # out of bounds or already water
grid[r][c] = '0' # sink this cell so we don't revisit it
dfs(r + 1, c)
dfs(r - 1, c)
dfs(r, c + 1)
dfs(r, c - 1)
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1':
count += 1 # found a new island
dfs(r, c) # sink the entire island
return count