Number of Islands

MediumGraph BFS/DFSBlind 75MidOpen on LeetCodeUpdated Sep 21, 2026

You're given an m x n grid where each cell is "1" (land) or "0" (water). An island is a group of land cells joined horizontally or vertically; cells that touch only diagonally are not connected. Everything outside the grid is water. Return the number of islands. You may modify the grid.

Examples

grid = [["1","1","0"],["1","0","0"],["0","0","1"]] returns 2

Land is colored. The top-left group and the lone bottom-right cell are the two islands.

The three land cells in the top left touch one another and form one island. The 1 in the bottom right touches no other land, so it is a second island.

grid = [["1","1","1"],["0","1","0"],["1","1","1"]] returns 1

The 1 in the center links the top row to the bottom row, so all seven land cells form a single island.

grid = [["1","0"],["0","1"]] returns 2

Touching at a corner doesn't connect two land cells.

The two land cells meet only at a corner. Diagonal contact doesn't join them, so each is its own island.

Constraints

1 <= m, n <= 300

Hints

Hint 1

Each land cell belongs to exactly one island, how would you mark everything in that island as you find it?

Hint 2

A pointer toward the approach

Hint 3

The full approach, step by step

Drill This: Your Approach First

Answer, Then Reveal

In two or three sentences, how would you solve it and what's the complexity?

Skip to Reading

Approach

Scan every cell. When you hit a "1", you've found a new island: count it, then run a depth-first search from it that turns every connected land cell into "0", so none of them is counted again. Each cell is sunk at most once, so the total work is O(m * n). Space is O(m * n) in the worst case for the recursion stack, when the grid is one big island.

Time

O(m * n)

Space

O(m * n)

Pitfall

The cells are the characters "1" and "0", not integers, so comparing against 1 counts nothing. Sink each cell before recursing into its neighbors, or two neighbors keep calling each other forever.

Solutions

class Solution {
    public int numIslands(char[][] grid) {
        int count = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    count++;
                    dfs(grid, i, j);
                }
            }
        }
        return count;
    }

    private void dfs(char[][] grid, int i, int j) {
        if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] != '1') return;
        grid[i][j] = '0';
        dfs(grid, i + 1, j);
        dfs(grid, i - 1, j);
        dfs(grid, i, j + 1);
        dfs(grid, i, j - 1);
    }
}

class Solution:
    def numIslands(self, grid) -> int:
        if not grid:
            return 0
        rows, cols = len(grid), len(grid[0])

        def dfs(i, j):
            if i < 0 or j < 0 or i >= rows or j >= cols or grid[i][j] != '1':
                return
            grid[i][j] = '0'
            dfs(i + 1, j); dfs(i - 1, j); dfs(i, j + 1); dfs(i, j - 1)

        count = 0
        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == '1':
                    count += 1
                    dfs(i, j)
        return count