Problem
Given an m×n 2D grid of “1”s (land) and “0”s (water), count the number of islands. An island is connected horizontally/vertically.
Example
Input: [["1","1","0"],["1","0","0"],["0","0","1"]]
Output: 2Solution
For each unvisited “1”, DFS to mark the entire island as visited. Each DFS launch counts as one island.
def num_islands(grid):
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] != '1': return
grid[r][c] = '0'
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':
dfs(r, c)
count += 1
return countfunction numIslands(grid) {
let count = 0;
function dfs(r, c) {
if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || grid[r][c] !== '1') return;
grid[r][c] = '0';
dfs(r+1, c); dfs(r-1, c); dfs(r, c+1); dfs(r, c-1);
}
for (let r = 0; r < grid.length; r++)
for (let c = 0; c < grid[0].length; c++)
if (grid[r][c] === '1') { dfs(r, c); count++; }
return count;
}void dfs(vector<vector<char>>& g, int r, int c) {
if (r < 0 || r >= g.size() || c < 0 || c >= g[0].size() || g[r][c] != '1') return;
g[r][c] = '0';
dfs(g, r+1, c); dfs(g, r-1, c); dfs(g, r, c+1); dfs(g, r, c-1);
}
int numIslands(vector<vector<char>>& grid) {
int count = 0;
for (int r = 0; r < grid.size(); r++)
for (int c = 0; c < grid[0].size(); c++)
if (grid[r][c] == '1') { dfs(grid, r, c); count++; }
return count;
}public int numIslands(char[][] grid) {
int count = 0;
for (int r = 0; r < grid.length; r++)
for (int c = 0; c < grid[0].length; c++)
if (grid[r][c] == '1') { dfs(grid, r, c); count++; }
return count;
}
private void dfs(char[][] g, int r, int c) {
if (r < 0 || r >= g.length || c < 0 || c >= g[0].length || g[r][c] != '1') return;
g[r][c] = '0';
dfs(g, r+1, c); dfs(g, r-1, c); dfs(g, r, c+1); dfs(g, r, c-1);
}Complexity
- Time: O(m * n)
- Space: O(m * n)
Explanation
Marking visited cells as “0” prevents recounting. The outer loops trigger a new DFS for each undiscovered island.
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?