Language Selection
Choose your preferred programming language
Showing: Python
Problem Statement
Given an m x n 2D binary grid which represents a map of ‘1’s (land) and ‘0’s (water), return the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are surrounded by water.
Input:
- 2D grid of characters ‘1’ (land) or ‘0’ (water)
Output:
- Number of islands (integer)
Constraints:
- 1 ≤ m, n ≤ 300
- grid[i][j] is ‘0’ or ‘1’
- All four edges 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: There is one connected 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
Explanation: There are three islands.
Example 3:
Input: grid = [["1"]]
Output: 1
Solutions
Approach 1: DFS (Depth-First Search)
Visit each land cell and explore all connected land cells using DFS, marking them as visited.
Algorithm:
- Iterate through each cell in the grid
- When finding an unvisited land cell (‘1’), increment island count
- Use DFS to mark all connected land cells as visited
- Continue until all cells are processed
Python:
def numIslands(grid):
"""
Count islands using DFS
Time: O(M × N)
Space: O(M × N) for recursion stack in worst case
"""
if not grid or not grid[0]:
return 0
rows, cols = len(grid), len(grid[0])
islands = 0
def dfs(r, c):
# Check bounds and if cell is water or visited
if (r < 0 or r >= rows or c < 0 or c >= cols or
grid[r][c] == '0'):
return
# Mark as visited by changing to '0'
grid[r][c] = '0'
# Explore all 4 directions
dfs(r + 1, c) # down
dfs(r - 1, c) # up
dfs(r, c + 1) # right
dfs(r, c - 1) # left
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1':
islands += 1
dfs(r, c)
return islands
def numIslandsIterative(grid):
"""
Count islands using iterative DFS
Time: O(M × N)
Space: O(min(M, N)) for stack
"""
if not grid or not grid[0]:
return 0
rows, cols = len(grid), len(grid[0])
islands = 0
def dfs_iterative(start_r, start_c):
stack = [(start_r, start_c)]
grid[start_r][start_c] = '0'
while stack:
r, c = stack.pop()
# Check all 4 directions
for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
nr, nc = r + dr, c + dc
if (0 <= nr < rows and 0 <= nc < cols and
grid[nr][nc] == '1'):
grid[nr][nc] = '0'
stack.append((nr, nc))
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1':
islands += 1
dfs_iterative(r, c)
return islands
Java:
class Solution {
/**
* Count islands using DFS
* Time: O(M × N)
* Space: O(M × N) for recursion stack
*/
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
int rows = grid.length;
int cols = grid[0].length;
int islands = 0;
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (grid[r][c] == '1') {
islands++;
dfs(grid, r, c);
}
}
}
return islands;
}
private void dfs(char[][] grid, int r, int c) {
int rows = grid.length;
int cols = grid[0].length;
if (r < 0 || r >= rows || c < 0 || c >= cols ||
grid[r][c] == '0') {
return;
}
grid[r][c] = '0'; // Mark as visited
dfs(grid, r + 1, c); // down
dfs(grid, r - 1, c); // up
dfs(grid, r, c + 1); // right
dfs(grid, r, c - 1); // left
}
/**
* Count islands using iterative DFS
* Time: O(M × N)
* Space: O(min(M, N))
*/
public int numIslandsIterative(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
int rows = grid.length;
int cols = grid[0].length;
int islands = 0;
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (grid[r][c] == '1') {
islands++;
dfsIterative(grid, r, c);
}
}
}
return islands;
}
private void dfsIterative(char[][] grid, int startR, int startC) {
int rows = grid.length;
int cols = grid[0].length;
Stack<int[]> stack = new Stack<>();
stack.push(new int[]{startR, startC});
grid[startR][startC] = '0';
int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
while (!stack.isEmpty()) {
int[] cell = stack.pop();
int r = cell[0], c = cell[1];
for (int[] dir : directions) {
int nr = r + dir[0];
int nc = c + dir[1];
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols &&
grid[nr][nc] == '1') {
grid[nr][nc] = '0';
stack.push(new int[]{nr, nc});
}
}
}
}
}
Go:
// numIslands - Count islands using DFS
// Time: O(M × N)
// Space: O(M × N)
func numIslands(grid [][]byte) int {
if len(grid) == 0 || len(grid[0]) == 0 {
return 0
}
rows, cols := len(grid), len(grid[0])
islands := 0
var dfs func(r, c int)
dfs = func(r, c int) {
if r < 0 || r >= rows || c < 0 || c >= cols ||
grid[r][c] == '0' {
return
}
grid[r][c] = '0' // Mark as visited
dfs(r+1, c) // down
dfs(r-1, c) // up
dfs(r, c+1) // right
dfs(r, c-1) // left
}
for r := 0; r < rows; r++ {
for c := 0; c < cols; c++ {
if grid[r][c] == '1' {
islands++
dfs(r, c)
}
}
}
return islands
}
// numIslandsIterative - Count islands using iterative DFS
// Time: O(M × N)
// Space: O(min(M, N))
func numIslandsIterative(grid [][]byte) int {
if len(grid) == 0 || len(grid[0]) == 0 {
return 0
}
rows, cols := len(grid), len(grid[0])
islands := 0
dfsIterative := func(startR, startC int) {
type Cell struct{ r, c int }
stack := []Cell{{startR, startC}}
grid[startR][startC] = '0'
directions := []Cell{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
for len(stack) > 0 {
cell := stack[len(stack)-1]
stack = stack[:len(stack)-1]
for _, dir := range directions {
nr, nc := cell.r+dir.r, cell.c+dir.c
if nr >= 0 && nr < rows && nc >= 0 && nc < cols &&
grid[nr][nc] == '1' {
grid[nr][nc] = '0'
stack = append(stack, Cell{nr, nc})
}
}
}
}
for r := 0; r < rows; r++ {
for c := 0; c < cols; c++ {
if grid[r][c] == '1' {
islands++
dfsIterative(r, c)
}
}
}
return islands
}
JavaScript:
/**
* Count islands using DFS
* Time: O(M × N)
* Space: O(M × N)
*/
function numIslands(grid) {
if (!grid || grid.length === 0) {
return 0;
}
const rows = grid.length;
const cols = grid[0].length;
let islands = 0;
function dfs(r, c) {
if (r < 0 || r >= rows || c < 0 || c >= cols ||
grid[r][c] === '0') {
return;
}
grid[r][c] = '0'; // Mark as visited
dfs(r + 1, c); // down
dfs(r - 1, c); // up
dfs(r, c + 1); // right
dfs(r, c - 1); // left
}
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (grid[r][c] === '1') {
islands++;
dfs(r, c);
}
}
}
return islands;
}
/**
* Count islands using iterative DFS
* Time: O(M × N)
* Space: O(min(M, N))
*/
function numIslandsIterative(grid) {
if (!grid || grid.length === 0) {
return 0;
}
const rows = grid.length;
const cols = grid[0].length;
let islands = 0;
function dfsIterative(startR, startC) {
const stack = [[startR, startC]];
grid[startR][startC] = '0';
const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];
while (stack.length > 0) {
const [r, c] = stack.pop();
for (const [dr, dc] of directions) {
const nr = r + dr;
const nc = c + dc;
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols &&
grid[nr][nc] === '1') {
grid[nr][nc] = '0';
stack.push([nr, nc]);
}
}
}
}
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (grid[r][c] === '1') {
islands++;
dfsIterative(r, c);
}
}
}
return islands;
}
C#:
public class Solution {
/// <summary>
/// Count islands using DFS
/// Time: O(M × N)
/// Space: O(M × N)
/// </summary>
public int NumIslands(char[][] grid) {
if (grid == null || grid.Length == 0) {
return 0;
}
int rows = grid.Length;
int cols = grid[0].Length;
int islands = 0;
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (grid[r][c] == '1') {
islands++;
Dfs(grid, r, c);
}
}
}
return islands;
}
private void Dfs(char[][] grid, int r, int c) {
int rows = grid.Length;
int cols = grid[0].Length;
if (r < 0 || r >= rows || c < 0 || c >= cols ||
grid[r][c] == '0') {
return;
}
grid[r][c] = '0'; // Mark as visited
Dfs(grid, r + 1, c); // down
Dfs(grid, r - 1, c); // up
Dfs(grid, r, c + 1); // right
Dfs(grid, r, c - 1); // left
}
/// <summary>
/// Count islands using iterative DFS
/// Time: O(M × N)
/// Space: O(min(M, N))
/// </summary>
public int NumIslandsIterative(char[][] grid) {
if (grid == null || grid.Length == 0) {
return 0;
}
int rows = grid.Length;
int cols = grid[0].Length;
int islands = 0;
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (grid[r][c] == '1') {
islands++;
DfsIterative(grid, r, c);
}
}
}
return islands;
}
private void DfsIterative(char[][] grid, int startR, int startC) {
int rows = grid.Length;
int cols = grid[0].Length;
Stack<(int r, int c)> stack = new Stack<(int, int)>();
stack.Push((startR, startC));
grid[startR][startC] = '0';
int[][] directions = new int[][] {
new int[] {1, 0}, new int[] {-1, 0},
new int[] {0, 1}, new int[] {0, -1}
};
while (stack.Count > 0) {
var (r, c) = stack.Pop();
foreach (var dir in directions) {
int nr = r + dir[0];
int nc = c + dir[1];
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols &&
grid[nr][nc] == '1') {
grid[nr][nc] = '0';
stack.Push((nr, nc));
}
}
}
}
}
Approach 2: BFS (Breadth-First Search)
Use BFS to explore each island level by level.
Python:
from collections import deque
def numIslandsBFS(grid):
"""
Count islands using BFS
Time: O(M × N)
Space: O(min(M, N))
"""
if not grid or not grid[0]:
return 0
rows, cols = len(grid), len(grid[0])
islands = 0
def bfs(start_r, start_c):
queue = deque([(start_r, start_c)])
grid[start_r][start_c] = '0'
while queue:
r, c = queue.popleft()
# Check all 4 directions
for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
nr, nc = r + dr, c + dc
if (0 <= nr < rows and 0 <= nc < cols and
grid[nr][nc] == '1'):
grid[nr][nc] = '0'
queue.append((nr, nc))
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1':
islands += 1
bfs(r, c)
return islands
Java:
public int numIslandsBFS(char[][] grid) {
/**
* Count islands using BFS
* Time: O(M × N)
* Space: O(min(M, N))
*/
if (grid == null || grid.length == 0) {
return 0;
}
int rows = grid.length;
int cols = grid[0].length;
int islands = 0;
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (grid[r][c] == '1') {
islands++;
bfs(grid, r, c);
}
}
}
return islands;
}
private void bfs(char[][] grid, int startR, int startC) {
int rows = grid.length;
int cols = grid[0].length;
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{startR, startC});
grid[startR][startC] = '0';
int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
while (!queue.isEmpty()) {
int[] cell = queue.poll();
int r = cell[0], c = cell[1];
for (int[] dir : directions) {
int nr = r + dir[0];
int nc = c + dir[1];
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols &&
grid[nr][nc] == '1') {
grid[nr][nc] = '0';
queue.offer(new int[]{nr, nc});
}
}
}
}
Go:
// numIslandsBFS - Count islands using BFS
// Time: O(M × N)
// Space: O(min(M, N))
func numIslandsBFS(grid [][]byte) int {
if len(grid) == 0 || len(grid[0]) == 0 {
return 0
}
rows, cols := len(grid), len(grid[0])
islands := 0
bfs := func(startR, startC int) {
type Cell struct{ r, c int }
queue := []Cell{{startR, startC}}
grid[startR][startC] = '0'
directions := []Cell{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
for len(queue) > 0 {
cell := queue[0]
queue = queue[1:]
for _, dir := range directions {
nr, nc := cell.r+dir.r, cell.c+dir.c
if nr >= 0 && nr < rows && nc >= 0 && nc < cols &&
grid[nr][nc] == '1' {
grid[nr][nc] = '0'
queue = append(queue, Cell{nr, nc})
}
}
}
}
for r := 0; r < rows; r++ {
for c := 0; c < cols; c++ {
if grid[r][c] == '1' {
islands++
bfs(r, c)
}
}
}
return islands
}
JavaScript:
/**
* Count islands using BFS
* Time: O(M × N)
* Space: O(min(M, N))
*/
function numIslandsBFS(grid) {
if (!grid || grid.length === 0) {
return 0;
}
const rows = grid.length;
const cols = grid[0].length;
let islands = 0;
function bfs(startR, startC) {
const queue = [[startR, startC]];
grid[startR][startC] = '0';
const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];
while (queue.length > 0) {
const [r, c] = queue.shift();
for (const [dr, dc] of directions) {
const nr = r + dr;
const nc = c + dc;
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols &&
grid[nr][nc] === '1') {
grid[nr][nc] = '0';
queue.push([nr, nc]);
}
}
}
}
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (grid[r][c] === '1') {
islands++;
bfs(r, c);
}
}
}
return islands;
}
C#:
public int NumIslandsBFS(char[][] grid) {
/// <summary>
/// Count islands using BFS
/// Time: O(M × N)
/// Space: O(min(M, N))
/// </summary>
if (grid == null || grid.Length == 0) {
return 0;
}
int rows = grid.Length;
int cols = grid[0].Length;
int islands = 0;
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (grid[r][c] == '1') {
islands++;
Bfs(grid, r, c);
}
}
}
return islands;
}
private void Bfs(char[][] grid, int startR, int startC) {
int rows = grid.Length;
int cols = grid[0].Length;
Queue<(int r, int c)> queue = new Queue<(int, int)>();
queue.Enqueue((startR, startC));
grid[startR][startC] = '0';
int[][] directions = new int[][] {
new int[] {1, 0}, new int[] {-1, 0},
new int[] {0, 1}, new int[] {0, -1}
};
while (queue.Count > 0) {
var (r, c) = queue.Dequeue();
foreach (var dir in directions) {
int nr = r + dir[0];
int nc = c + dir[1];
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols &&
grid[nr][nc] == '1') {
grid[nr][nc] = '0';
queue.Enqueue((nr, nc));
}
}
}
}
Approach 3: Union-Find
Use Union-Find data structure to connect land cells and count disjoint sets.
Python:
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
self.count = 0
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py:
return
if self.rank[px] < self.rank[py]:
px, py = py, px
self.parent[py] = px
if self.rank[px] == self.rank[py]:
self.rank[px] += 1
self.count -= 1
def add_land(self):
self.count += 1
def numIslandsUnionFind(grid):
"""
Count islands using Union-Find
Time: O(M × N × α(M×N))
Space: O(M × N)
"""
if not grid or not grid[0]:
return 0
rows, cols = len(grid), len(grid[0])
uf = UnionFind(rows * cols)
# First pass: mark all land cells
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1':
uf.add_land()
# Second pass: union adjacent land cells
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1':
idx = r * cols + c
# Check right and down neighbors only
if c + 1 < cols and grid[r][c + 1] == '1':
uf.union(idx, idx + 1)
if r + 1 < rows and grid[r + 1][c] == '1':
uf.union(idx, idx + cols)
return uf.count
Java:
class UnionFind {
int[] parent;
int[] rank;
int count;
public UnionFind(int n) {
parent = new int[n];
rank = new int[n];
count = 0;
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
public int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
public void union(int x, int y) {
int px = find(x);
int py = find(y);
if (px == py) return;
if (rank[px] < rank[py]) {
int temp = px;
px = py;
py = temp;
}
parent[py] = px;
if (rank[px] == rank[py]) {
rank[px]++;
}
count--;
}
public void addLand() {
count++;
}
}
public int numIslandsUnionFind(char[][] grid) {
/**
* Count islands using Union-Find
* Time: O(M × N × α(M×N))
* Space: O(M × N)
*/
if (grid == null || grid.length == 0) {
return 0;
}
int rows = grid.length;
int cols = grid[0].length;
UnionFind uf = new UnionFind(rows * cols);
// First pass: mark all land cells
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (grid[r][c] == '1') {
uf.addLand();
}
}
}
// Second pass: union adjacent land cells
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (grid[r][c] == '1') {
int idx = r * cols + c;
if (c + 1 < cols && grid[r][c + 1] == '1') {
uf.union(idx, idx + 1);
}
if (r + 1 < rows && grid[r + 1][c] == '1') {
uf.union(idx, idx + cols);
}
}
}
}
return uf.count;
}
Key Insights
- Connected Components: Each island is a connected component of land cells
- Graph Traversal: Both DFS and BFS effectively explore connected components
- In-place Marking: Modifying the grid to mark visited cells saves space
- 4-directional Movement: Only horizontal and vertical connections count
Edge Cases
- Empty grid: Return 0
- All water: Return 0
- All land: Return 1 (single island)
- Single cell: Return 0 or 1 based on cell value
- Diagonal islands: Not connected (only 4-directional)
Common Mistakes
- Not checking bounds: Array out of bounds errors
- Diagonal connections: Including diagonal neighbors incorrectly
- Not marking visited: Infinite recursion or revisiting cells
- Modifying input: Not restoring grid if required
Follow-up Questions
- Perimeter of island: Calculate the total perimeter
- Max area island: Find the island with maximum area
- Number of distinct islands: Count unique island shapes
- Surrounded regions: Find regions completely surrounded by land
- Dynamic islands: Handle adding/removing land cells dynamically