Number of Islands

medium
GraphsGraphDepth-First SearchBreadth-First SearchMatrix

Given an m x n 2D binary grid 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.

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 are connected, forming a single 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 separate groups of connected land cells, so there are three islands.

Constraints

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

Approaches

2 worked solutions ranked from straightforward to optimal — each with intuition, algorithm, complexity, and verified code in C++, Java, Python, and Go.

Approach 1

DFS Flood Fill

Intuition

We iterate through every cell in the grid. When we find a land cell '1' that hasn't been visited yet, we've discovered a new island. We then run DFS from that cell to mark all connected land cells as visited (by changing them to '0'), effectively "sinking" the entire island. Each time we trigger a new DFS, we increment our island count. This flood-fill approach is intuitive because it mirrors how we'd visually identify islands -- find a piece of land, trace its entire boundary, then look for the next one.

Algorithm

  1. Initialize an island counter to 0.
  2. Iterate through each cell in the grid.
  3. When a cell with value `'1'` is found, increment the island counter.
  4. Run DFS from that cell: mark it as `'0'` (visited), then recursively visit all four adjacent cells that contain `'1'`.
  5. After the DFS completes, all land in this island has been marked. Continue scanning for the next unvisited `'1'`.
  6. Return the island counter.
TimeO(m * n) where m and n are the dimensions of the gridSpaceO(m * n) for the recursion stack in the worst case

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int count = 0;

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

        return count;
    }

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

        grid[r][c] = '0';
        dfs(grid, r + 1, c);
        dfs(grid, r - 1, c);
        dfs(grid, r, c + 1);
        dfs(grid, r, c - 1);
    }
};
Java 21
class Solution {
    public int numIslands(char[][] grid) {
        int m = grid.length, n = grid[0].length;
        int count = 0;

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

        return count;
    }

    private void dfs(char[][] grid, int r, int c) {
        int m = grid.length, n = grid[0].length;
        if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] == '0') return;

        grid[r][c] = '0';
        dfs(grid, r + 1, c);
        dfs(grid, r - 1, c);
        dfs(grid, r, c + 1);
        dfs(grid, r, c - 1);
    }
}
Python 3.12
from typing import List


class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
        count = 0

        def dfs(r, c):
            if r < 0 or r >= m or c < 0 or c >= n or grid[r][c] == '0':
                return
            grid[r][c] = '0'
            dfs(r + 1, c)
            dfs(r - 1, c)
            dfs(r, c + 1)
            dfs(r, c - 1)

        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1':
                    count += 1
                    dfs(i, j)

        return count
Go 1.26
func numIslands(grid [][]byte) int {
    m, n := len(grid), len(grid[0])
    count := 0

    var dfs func(r, c int)
    dfs = func(r, c int) {
        if r < 0 || r >= m || c < 0 || c >= n || grid[r][c] == '0' {
            return
        }
        grid[r][c] = '0'
        dfs(r+1, c)
        dfs(r-1, c)
        dfs(r, c+1)
        dfs(r, c-1)
    }

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

    return count
}
Approach 2

BFS Flood Fill

Intuition

Instead of recursive DFS, we can use BFS with a queue to explore each island. When we encounter an unvisited land cell, we add it to a queue and process all connected land cells level by level. BFS naturally explores the island outward from the starting point. This approach avoids potential stack overflow issues from deep recursion on very large grids while maintaining the same time complexity.

Algorithm

  1. Initialize an island counter to 0.
  2. Iterate through each cell in the grid.
  3. When a cell with value `'1'` is found, increment the counter and add the cell to a queue.
  4. While the queue is not empty, dequeue a cell, and for each of its four neighbors that contain `'1'`, mark them as `'0'` and enqueue them.
  5. When the queue is empty, the entire island has been processed. Continue scanning.
  6. Return the island counter.
TimeO(m * n) where m and n are the dimensions of the gridSpaceO(min(m, n)) for the queue in the worst case

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int count = 0;
        int dirs[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    count++;
                    grid[i][j] = '0';
                    queue<pair<int, int>> q;
                    q.push({i, j});

                    while (!q.empty()) {
                        auto [r, c] = q.front();
                        q.pop();
                        for (auto& d : dirs) {
                            int nr = r + d[0], nc = c + d[1];
                            if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == '1') {
                                grid[nr][nc] = '0';
                                q.push({nr, nc});
                            }
                        }
                    }
                }
            }
        }

        return count;
    }
};
Java 21
class Solution {
    public int numIslands(char[][] grid) {
        int m = grid.length, n = grid[0].length;
        int count = 0;
        int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    count++;
                    grid[i][j] = '0';
                    Queue<int[]> queue = new LinkedList<>();
                    queue.add(new int[]{i, j});

                    while (!queue.isEmpty()) {
                        int[] cell = queue.poll();
                        for (int[] d : dirs) {
                            int nr = cell[0] + d[0], nc = cell[1] + d[1];
                            if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == '1') {
                                grid[nr][nc] = '0';
                                queue.add(new int[]{nr, nc});
                            }
                        }
                    }
                }
            }
        }

        return count;
    }
}
Python 3.12
from typing import List
from collections import deque


class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
        count = 0

        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1':
                    count += 1
                    grid[i][j] = '0'
                    queue = deque([(i, j)])

                    while queue:
                        r, c = queue.popleft()
                        for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                            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 count
Go 1.26
func numIslands(grid [][]byte) int {
    m, n := len(grid), len(grid[0])
    count := 0
    dirs := [][2]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}

    type cell struct{ r, c int }

    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if grid[i][j] == '1' {
                count++
                grid[i][j] = '0'
                queue := []cell{{i, j}}

                for len(queue) > 0 {
                    curr := queue[0]
                    queue = queue[1:]
                    for _, d := range dirs {
                        nr, nc := curr.r+d[0], curr.c+d[1]
                        if nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == '1' {
                            grid[nr][nc] = '0'
                            queue = append(queue, cell{nr, nc})
                        }
                    }
                }
            }
        }
    }

    return count
}

Frequently asked questions

What is the optimal time complexity of Number of Islands?

The most efficient approach in this guide ("BFS Flood Fill") runs in O(m * n) where m and n are the dimensions of the grid time and uses O(min(m, n)) for the queue in the worst case extra space. Earlier brute-force approaches are slower; see all 2 approaches above for the full progression.

What pattern does Number of Islands use?

Number of Islands is a medium-level Graphs problem involving Graph, Depth-First Search, Breadth-First Search. Recognizing the pattern is half the work — see the intuition section above for how to spot it.

Can Number of Islands be solved without extra space?

The most space-efficient approach in this guide uses O(min(m, n)) for the queue in the worst case extra space (excluding the input). If you're aiming for in-place — see the trade-off in the algorithm section above — the brute-force approach uses O(m * n) for the recursion stack in the worst case, while the optimized version uses O(min(m, n)) for the queue in the worst case.

Which programming languages does this Ratta solution support?

Every approach above ships with verified, runnable solutions in C++, Java, Python, and Go. The starter templates in the workspace match the same four languages so you can practice in your interview language of choice.

Related Problems

Pacific Atlantic Water Flow

Original problem: leetcode.com

Loading editor...
Input
grid=
[["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]]
Expected Output
1