Number of Islands

Problem Statement

Given an m x n 2D binary grid grid where '1' represents land and '0' represents water, return the number of islands.

An island is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are surrounded by water.

What to notice first

• Each cell is connected to at most 4 neighbors (up, down, left, right).
• When you find a land cell, you need to mark all connected land cells as visited to count it as one island.
• This is a classic connected components problem on a 2D grid.

Examples

Grid	Output	Explanation
[["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]]	1	All four 1s are connected, forming one island
[["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]	3	Three separate islands

Constraints

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 300
• grid[i][j] is '0' or '1'

Real-World Applications

Where this pattern appears

• Geographic information systems (GIS) — identifying landmasses and water bodies.
• Image processing — finding connected components (blob detection).
• Social networks — identifying connected communities.
• Game development — finding playable regions in terrain.

Complexity Comparison

Approach	Time	Space	Notes
DFS (Recursive)	O(m * n)	O(m * n)	Call stack depth in worst case, intuitive
BFS (Queue-based)	O(m * n)	O(m * n)	Explicit queue, iterative traversal

* m = rows, n = columns

Which approach should you learn first?

• Pick DFS if you want the most straightforward, recursive solution.
• Pick BFS if you prefer an iterative approach with explicit queue management.

Most Intuitive

DFS (Recursive)

O(m * n) time · O(m * n) space

Iterative

BFS (Queue)

O(m * n) time · O(m * n) space

Approach 1: DFS (Depth-First Search) — Recommended

★ Recommended

Use recursive DFS to explore each island completely before moving to the next unvisited land cell. Mark visited cells to avoid counting them multiple times.

⏱ Time O(m * n) Visit each cell once 💾 Space O(m * n) Recursion stack + grid marking

Step-by-step Example

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

Step 1: Scan grid, find "1" at (0, 0)
Step 2: DFS from (0, 0) → marks (0, 0), (0, 1), (1, 1) as visited → Count = 1
Step 3: Continue scan, find "1" at (2, 0)
Step 4: DFS from (2, 0) → marks (2, 0) → Count = 2
Step 5: Continue scan, find "1" at (2, 2)
Step 6: DFS from (2, 2) → marks (2, 2) → Count = 3
Result: 3 islands

Pseudocode

function numIslandsDFS(grid):
    if grid is empty:
        return 0

    count = 0
    for i from 0 to rows - 1:
        for j from 0 to cols - 1:
            if grid[i][j] == '1':
                dfs(grid, i, j)
                count += 1

    return count

function dfs(grid, i, j):
    if i < 0 or i >= rows or j < 0 or j >= cols or grid[i][j] == '0':
        return

    grid[i][j] = '0'  // Mark as visited
    dfs(grid, i + 1, j)
    dfs(grid, i - 1, j)
    dfs(grid, i, j + 1)
    dfs(grid, i, j - 1)

Solution Code

Python

number_of_islands_dfs.py

def num_islands_dfs(grid: list[list[str]]) -> int:
    """
    DFS approach - recursively explore each island from any land cell.
    Time: O(m * n) - visit each cell once
    Space: O(m * n) - recursion call stack in worst case
    """
    if not grid or not grid[0]:
        return 0

    rows, cols = len(grid), len(grid[0])
    count = 0

    def dfs(r: int, c: int) -> None:
        """Mark all connected land cells as visited."""
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == '0':
            return

        grid[r][c] = '0'  # Mark as visited

        # Explore all 4 directions
        dfs(r + 1, c)  # Down
        dfs(r - 1, c)  # Up
        dfs(r, c + 1)  # Right
        dfs(r, c - 1)  # Left

    # Find and count islands
    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == '1':
                dfs(i, j)
                count += 1

    return count


# Test cases
grid1 = [["1","1","1","1","0"],
         ["1","1","0","1","0"],
         ["1","1","0","0","0"],
         ["0","0","0","0","0"]]
print(num_islands_dfs(grid1))  # 1

grid2 = [["1","1","0","0","0"],
         ["1","1","0","0","0"],
         ["0","0","1","0","0"],
         ["0","0","0","1","1"]]
print(num_islands_dfs(grid2))  # 3

C++

number_of_islands_dfs.cpp

#include <vector>
using namespace std;

class NumberOfIslandsDFS {
public:
    int numIslands(vector<vector<char>>& grid) {
        /**
         * DFS approach - recursively explore each island.
         * Time: O(m * n) - visit each cell once
         * Space: O(m * n) - recursion call stack
         */
        if (grid.empty() || grid[0].empty()) return 0;

        int rows = grid.size();
        int cols = grid[0].size();
        int count = 0;

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == '1') {
                    dfs(grid, i, j, rows, cols);
                    count++;
                }
            }
        }

        return count;
    }

private:
    void dfs(vector<vector<char>>& grid, int r, int c, int rows, int cols) {
        if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] == '0')
            return;

        grid[r][c] = '0';  // Mark as visited

        // Explore 4 directions
        dfs(grid, r + 1, c, rows, cols);
        dfs(grid, r - 1, c, rows, cols);
        dfs(grid, r, c + 1, rows, cols);
        dfs(grid, r, c - 1, rows, cols);
    }
};

Java

NumberOfIslandsDFS.java

class NumberOfIslandsDFS {
    /**
     * DFS approach - recursively explore each island.
     * Time: O(m * n) - visit each cell once
     * Space: O(m * n) - recursion call stack
     */
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) return 0;

        int rows = grid.length;
        int cols = grid[0].length;
        int count = 0;

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == '1') {
                    dfs(grid, i, j, rows, cols);
                    count++;
                }
            }
        }

        return count;
    }

    private void dfs(char[][] grid, int r, int c, int rows, int cols) {
        if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] == '0')
            return;

        grid[r][c] = '0';  // Mark as visited

        // Explore 4 directions
        dfs(grid, r + 1, c, rows, cols);
        dfs(grid, r - 1, c, rows, cols);
        dfs(grid, r, c + 1, rows, cols);
        dfs(grid, r, c - 1, rows, cols);
    }
}

JavaScript

number_of_islands_dfs.js

/**
 * DFS approach - recursively explore each island.
 * Time: O(m * n) - visit each cell once
 * Space: O(m * n) - recursion call stack
 */
function numIslandsDFS(grid) {
    if (!grid || grid.length === 0) return 0;

    const rows = grid.length;
    const cols = grid[0].length;
    let count = 0;

    const dfs = (r, c) => {
        if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] === '0')
            return;

        grid[r][c] = '0';  // Mark as visited

        // Explore 4 directions
        dfs(r + 1, c);
        dfs(r - 1, c);
        dfs(r, c + 1);
        dfs(r, c - 1);
    };

    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            if (grid[i][j] === '1') {
                dfs(i, j);
                count++;
            }
        }
    }

    return count;
}

// Test cases
const grid1 = [["1","1","1","1","0"],
               ["1","1","0","1","0"],
               ["1","1","0","0","0"],
               ["0","0","0","0","0"]];
console.log(numIslandsDFS(grid1));  // 1

const grid2 = [["1","1","0","0","0"],
               ["1","1","0","0","0"],
               ["0","0","1","0","0"],
               ["0","0","0","1","1"]];
console.log(numIslandsDFS(grid2));  // 3

Rust

number_of_islands_dfs.rs

/**
 * DFS approach - recursively explore each island.
 * Time: O(m * n) - visit each cell once
 * Space: O(m * n) - recursion call stack
 */
impl Solution {
    pub fn num_islands(grid: &mut Vec<Vec<char>>) -> i32 {
        if grid.is_empty() || grid[0].is_empty() {
            return 0;
        }

        let rows = grid.len();
        let cols = grid[0].len();
        let mut count = 0;

        for i in 0..rows {
            for j in 0..cols {
                if grid[i][j] == '1' {
                    Self::dfs(grid, i, j, rows, cols);
                    count += 1;
                }
            }
        }

        count
    }

    fn dfs(grid: &mut Vec<Vec<char>>, r: usize, c: usize, rows: usize, cols: usize) {
        if r >= rows || c >= cols || grid[r][c] == '0' {
            return;
        }

        grid[r][c] = '0';  // Mark as visited

        // Explore 4 directions
        if r > 0 {
            Self::dfs(grid, r - 1, c, rows, cols);
        }
        Self::dfs(grid, r + 1, c, rows, cols);
        if c > 0 {
            Self::dfs(grid, r, c - 1, rows, cols);
        }
        Self::dfs(grid, r, c + 1, rows, cols);
    }
}

pub struct Solution;

Go

number_of_islands_dfs.go

package main

/**
 * DFS approach - recursively explore each island.
 * Time: O(m * n) - visit each cell once
 * Space: O(m * n) - recursion call stack
 */
func numIslandsDFS(grid [][]byte) int {
    if len(grid) == 0 || len(grid[0]) == 0 {
        return 0
    }

    rows := len(grid)
    cols := len(grid[0])
    count := 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

        // Explore 4 directions
        dfs(r+1, c)
        dfs(r-1, c)
        dfs(r, c+1)
        dfs(r, c-1)
    }

    for i := 0; i < rows; i++ {
        for j := 0; j < cols; j++ {
            if grid[i][j] == '1' {
                dfs(i, j)
                count++
            }
        }
    }

    return count
}

Approach 2: BFS (Breadth-First Search)

✓ Simple

Use a queue-based BFS to explore each island level by level. Mark cells as visited when they are enqueued to avoid duplicate processing.

⏱ Time O(m * n) Visit each cell once 💾 Space O(m * n) Queue storage + grid marking

Step-by-step Example

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

Step 1: Scan grid, find "1" at (0, 0)
Step 2: BFS from (0, 0) using queue → processes (0, 0), (0, 1), (1, 1) → Count = 1
Step 3: Continue scan, find "1" at (2, 0)
Step 4: BFS from (2, 0) using queue → processes (2, 0) → Count = 2
Step 5: Continue scan, find "1" at (2, 2)
Step 6: BFS from (2, 2) using queue → processes (2, 2) → Count = 3
Result: 3 islands

Pseudocode

function numIslandsBFS(grid):
    if grid is empty:
        return 0

    count = 0
    for i from 0 to rows - 1:
        for j from 0 to cols - 1:
            if grid[i][j] == '1':
                bfs(grid, i, j)
                count += 1

    return count

function bfs(grid, i, j):
    queue = [（i, j)]
    grid[i][j] = '0'  // Mark as visited

    while queue is not empty:
        row, col = queue.dequeue()
        for each direction (up, down, left, right):
            newRow, newCol = row + dr, col + dc
            if valid(newRow, newCol) and grid[newRow][newCol] == '1':
                grid[newRow][newCol] = '0'  // Mark as visited
                queue.enqueue((newRow, newCol))

Solution Code

Python

number_of_islands_bfs.py

from collections import deque

def num_islands_bfs(grid: list[list[str]]) -> int:
    """
    BFS approach - use queue to explore each island level by level.
    Time: O(m * n) - visit each cell once
    Space: O(m * n) - queue storage
    """
    if not grid or not grid[0]:
        return 0

    rows, cols = len(grid), len(grid[0])
    count = 0

    def bfs(start_r: int, start_c: int) -> None:
        """Mark all connected land cells as visited using BFS."""
        queue = deque([(start_r, start_c)])
        grid[start_r][start_c] = '0'  # Mark as visited

        while queue:
            r, c = queue.popleft()

            # Explore 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'  # Mark as visited
                    queue.append((nr, nc))

    # Find and count islands
    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == '1':
                bfs(i, j)
                count += 1

    return count


# Test cases
grid1 = [["1","1","1","1","0"],
         ["1","1","0","1","0"],
         ["1","1","0","0","0"],
         ["0","0","0","0","0"]]
print(num_islands_bfs(grid1))  # 1

grid2 = [["1","1","0","0","0"],
         ["1","1","0","0","0"],
         ["0","0","1","0","0"],
         ["0","0","0","1","1"]]
print(num_islands_bfs(grid2))  # 3

C++

number_of_islands_bfs.cpp

#include <vector>
#include <queue>
using namespace std;

class NumberOfIslandsBFS {
public:
    int numIslands(vector<vector<char>>& grid) {
        /**
         * BFS approach - use queue to explore each island level by level.
         * Time: O(m * n) - visit each cell once
         * Space: O(m * n) - queue storage
         */
        if (grid.empty() || grid[0].empty()) return 0;

        int rows = grid.size();
        int cols = grid[0].size();
        int count = 0;

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == '1') {
                    bfs(grid, i, j, rows, cols);
                    count++;
                }
            }
        }

        return count;
    }

private:
    void bfs(vector<vector<char>>& grid, int sr, int sc, int rows, int cols) {
        queue<pair<int, int>> q;
        q.push({sr, sc});
        grid[sr][sc] = '0';

        int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

        while (!q.empty()) {
            auto [r, c] = q.front();
            q.pop();

            for (auto& dir : dirs) {
                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';
                    q.push({nr, nc});
                }
            }
        }
    }
};

Java

NumberOfIslandsBFS.java

import java.util.Queue;
import java.util.LinkedList;

class NumberOfIslandsBFS {
    /**
     * BFS approach - use queue to explore each island level by level.
     * Time: O(m * n) - visit each cell once
     * Space: O(m * n) - queue storage
     */
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) return 0;

        int rows = grid.length;
        int cols = grid[0].length;
        int count = 0;

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == '1') {
                    bfs(grid, i, j, rows, cols);
                    count++;
                }
            }
        }

        return count;
    }

    private void bfs(char[][] grid, int sr, int sc, int rows, int cols) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{sr, sc});
        grid[sr][sc] = '0';

        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            int r = curr[0];
            int c = curr[1];

            for (int[] dir : dirs) {
                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});
                }
            }
        }
    }
}

JavaScript

number_of_islands_bfs.js

/**
 * BFS approach - use queue to explore each island level by level.
 * Time: O(m * n) - visit each cell once
 * Space: O(m * n) - queue storage
 */
function numIslandsBFS(grid) {
    if (!grid || grid.length === 0) return 0;

    const rows = grid.length;
    const cols = grid[0].length;
    let count = 0;

    const bfs = (sr, sc) => {
        const queue = [[sr, sc]];
        grid[sr][sc] = '0';

        const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];

        while (queue.length > 0) {
            const [r, c] = queue.shift();

            for (const [dr, dc] of dirs) {
                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 i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            if (grid[i][j] === '1') {
                bfs(i, j);
                count++;
            }
        }
    }

    return count;
}

// Test cases
const grid1 = [["1","1","1","1","0"],
               ["1","1","0","1","0"],
               ["1","1","0","0","0"],
               ["0","0","0","0","0"]];
console.log(numIslandsBFS(grid1));  // 1

const grid2 = [["1","1","0","0","0"],
               ["1","1","0","0","0"],
               ["0","0","1","0","0"],
               ["0","0","0","1","1"]];
console.log(numIslandsBFS(grid2));  // 3

Rust

number_of_islands_bfs.rs

use std::collections::VecDeque;

/**
 * BFS approach - use queue to explore each island level by level.
 * Time: O(m * n) - visit each cell once
 * Space: O(m * n) - queue storage
 */
impl Solution {
    pub fn num_islands(grid: &mut Vec<Vec<char>>) -> i32 {
        if grid.is_empty() || grid[0].is_empty() {
            return 0;
        }

        let rows = grid.len();
        let cols = grid[0].len();
        let mut count = 0;

        for i in 0..rows {
            for j in 0..cols {
                if grid[i][j] == '1' {
                    Self::bfs(grid, i, j, rows, cols);
                    count += 1;
                }
            }
        }

        count
    }

    fn bfs(grid: &mut Vec<Vec<char>>, sr: usize, sc: usize, rows: usize, cols: usize) {
        let mut queue = VecDeque::new();
        queue.push_back((sr, sc));
        grid[sr][sc] = '0';

        let dirs = [(1, 0), (-1, 0isize), (0, 1), (0, -1)];

        while let Some((r, c)) = queue.pop_front() {
            for (dr, dc) in dirs.iter() {
                let nr = if *dr >= 0 {
                    r + (*dr as usize)
                } else if r > (-*dr) as usize {
                    r - ((-*dr) as usize)
                } else {
                    continue;
                };

                let nc = if *dc >= 0 {
                    c + (*dc as usize)
                } else if c > (-*dc) as usize {
                    c - ((-*dc) as usize)
                } else {
                    continue;
                };

                if nr < rows && nc < cols && grid[nr][nc] == '1' {
                    grid[nr][nc] = '0';
                    queue.push_back((nr, nc));
                }
            }
        }
    }
}

pub struct Solution;

Go

number_of_islands_bfs.go

package main

/**
 * BFS approach - use queue to explore each island level by level.
 * Time: O(m * n) - visit each cell once
 * Space: O(m * n) - queue storage
 */
func numIslandsBFS(grid [][]byte) int {
    if len(grid) == 0 || len(grid[0]) == 0 {
        return 0
    }

    rows := len(grid)
    cols := len(grid[0])
    count := 0

    bfs := func(sr, sc int) {
        queue := [][2]int{{sr, sc}}
        grid[sr][sc] = '0'

        dirs := [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}

        for len(queue) > 0 {
            r, c := queue[0][0], queue[0][1]
            queue = queue[1:]

            for _, dir := range dirs {
                nr := r + dir[0]
                nc := c + dir[1]

                if nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == '1' {
                    grid[nr][nc] = '0'
                    queue = append(queue, [2]int{nr, nc})
                }
            }
        }
    }

    for i := 0; i < rows; i++ {
        for j := 0; j < cols; j++ {
            if grid[i][j] == '1' {
                bfs(i, j)
                count++
            }
        }
    }

    return count
}

Related Problems

• Surrounded Regions ↗ Medium #130
• Clone Graph ↗ Medium #133
• Max Area of Island ↗ Medium #695
• Making A Large Island ↗ Hard #827

Interview Tips

Key trade-offs to discuss

• DFS vs BFS: DFS is simpler to write and uses recursion; BFS is iterative and shows understanding of queue mechanics.
• Space complexity: Both are O(m*n) in worst case, but DFS has implicit call stack while BFS has explicit queue.
• Mutating input: Modifying the grid to mark visited cells saves space but destroys original input. Discuss using a visited set instead.
• Follow-up: Can you find the area of the largest island? Can you count islands without modifying the grid?

Next
#130 Surrounded Regions →