Number of Islands

mediumGraphs: BFS / DFS207 stepsJava · Python · C++

Count groups of connected land cells. Scan the grid; each time you find unvisited land, that's a new island. DFS from it and sink every connected land cell (turn it to water) so it's never counted again.

▶ Watch the animated trace

Traced input: grid = [[1,1,0,0,0],[1,1,0,0,0],[0,0,1,0,0],[0,0,0,1,1]] → 3. Original problem: neetcode.io/problems/count-number-of-islands

Complexity

BestO(m·n)

AverageO(m·n)

WorstO(m·n)

SpaceO(m·n)

Each cell is visited a constant number of times; recursion depth can reach m·n.

Key idea

An island is a connected component of '1' cells (4-directional).
The outer scan finds a new island each time it hits a '1'.
DFS sinks the whole island, marking it visited in place.
BFS or union-find work equally well.

Common mistakes

Counting cells instead of islands.
Using diagonal neighbours.
Very large grids can overflow the recursion stack; BFS avoids that.

Solution

Java

// DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}: down, up, right, left
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') {
                count++;
                sink(grid, r, c);
            }
        }
    }
    return count;
}

void sink(char[][] grid, int r, int c) {
    if (r < 0 || c < 0 || r >= grid.length || c >= grid[0].length || grid[r][c] != '1') return;
    grid[r][c] = '0';
    for (int[] d : DIRS) sink(grid, r + d[0], c + d[1]);
}

Python

# DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)]: down, up, right, left
def numIslands(grid: List[List[str]]) -> int:
    def sink(r: int, c: int) -> None:
        if r < 0 or c < 0 or r >= len(grid) or c >= len(grid[0]) or grid[r][c] != '1': return
        grid[r][c] = '0'
        for dr, dc in DIRS: sink(r + dr, c + dc)

    count = 0
    for r in range(len(grid)):
        for c in range(len(grid[0])):
            if grid[r][c] == '1':
                count += 1
                sink(r, c)
    return count

C++

// DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}: down, up, right, left
void sink(vector<vector<char>>& grid, int r, int c) {
    if (r < 0 || c < 0 || r >= (int)grid.size() || c >= (int)grid[0].size() || grid[r][c] != '1') return;
    grid[r][c] = '0';
    for (auto& d : DIRS) sink(grid, r + d[0], c + d[1]);
}

int numIslands(vector<vector<char>>& grid) {
    int count = 0;
    for (int r = 0; r < (int)grid.size(); r++) {
        for (int c = 0; c < (int)grid[0].size(); c++) {
            if (grid[r][c] == '1') {
                count++;
                sink(grid, r, c);
            }
        }
    }
    return count;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
All water The scan never finds land.	`grid = [[0, 0], [0, 0]]`	`0`
All land One DFS sinks everything.	`grid = [[1, 1], [1, 1]]`	`1`
Diagonal cells Diagonal touches don't connect.	`grid = [[1, 0], [0, 1]]`	`2`
Snake-shaped island The DFS follows the bend.	`grid = [[1,1,1],[0,0,1],[1,1,1]]`	`1`