Problem statement

Given an m x n grid of 1s (land) and 0s (water), return the number of islands — groups of land connected horizontally or vertically. The grid edges are surrounded by water.

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

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

Constraints

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

Hints for Number of Islands

1. Hint 1

   Every time you meet unvisited land, that's a new island — flood it away.

2. Hint 2

   DFS/BFS marking visited land avoids counting a cell twice.

How to solve Number of Islands

An island is a connected component of land. Sweep the grid, and each time you meet a land cell that has not been absorbed yet, you have found a component nobody has counted — increment the answer and sink the whole island so it is never counted again.

Approach

1. Scan every cell in row-major order.
2. Skip water and land already sunk.
3. On fresh land, increment the island counter.
4. Flood the component with a stack or queue, turning each visited land cell into water as it is pushed.
5. Continue the outer scan; the counter is the answer.

Why it works

Sinking land as it is visited doubles as the visited marker, so each cell is processed once and the flood reaches exactly the component of its seed. That makes the outer loop start a traversal exactly once per island — never twice, because every other cell of that island is already water by the time the scan reaches it.

Complexity

• Time — O(rows · cols)
• Space — O(rows · cols)

Pitfalls

• Sink cells when you push them, not when you pop, or the same cell enters the frontier repeatedly.
• Connectivity is 4-directional; counting diagonals merges islands that should stay separate.
• If mutating the input is unacceptable, keep a separate visited grid — but then you must check it as well as the land value.
• Bounds-check all four neighbours; the grid edge is water by definition, not by indexing luck.

Reference solution

Python

from typing import List

def numIslands(grid: List[List[int]]) -> int:
    g = [row[:] for row in grid]
    count = 0

    def sink(i, j):
        if i < 0 or j < 0 or i >= len(g) or j >= len(g[0]) or g[i][j] != 1:
            return
        g[i][j] = 0
        sink(i + 1, j)
        sink(i - 1, j)
        sink(i, j + 1)
        sink(i, j - 1)

    for i in range(len(g)):
        for j in range(len(g[0])):
            if g[i][j] == 1:
                count += 1
                sink(i, j)
    return count

Java

public static int numIslands(int[][] grid) {
    int rows = grid.length, cols = grid[0].length, islands = 0;
    int[] dr = {-1, 1, 0, 0};
    int[] dc = {0, 0, -1, 1};
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (grid[i][j] != 1) continue;
            islands++;
            Deque<int[]> stack = new ArrayDeque<>();
            stack.push(new int[]{i, j});
            grid[i][j] = 0;
            while (!stack.isEmpty()) {
                int[] cell = stack.pop();
                for (int d = 0; d < 4; d++) {
                    int nr = cell[0] + dr[d], nc = cell[1] + dc[d];
                    if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 1) {
                        grid[nr][nc] = 0;
                        stack.push(new int[]{nr, nc});
                    }
                }
            }
        }
    }
    return islands;
}

C++

int numIslands(vector<vector<int>>& grid) {
    int rows = (int) grid.size(), cols = (int) grid[0].size(), islands = 0;
    int dr[4] = {-1, 1, 0, 0};
    int dc[4] = {0, 0, -1, 1};
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (grid[i][j] != 1) continue;
            islands++;
            vector<pair<int, int>> stack;
            stack.push_back(make_pair(i, j));
            grid[i][j] = 0;
            while (!stack.empty()) {
                pair<int, int> cell = stack.back();
                stack.pop_back();
                for (int d = 0; d < 4; d++) {
                    int nr = cell.first + dr[d], nc = cell.second + dc[d];
                    if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 1) {
                        grid[nr][nc] = 0;
                        stack.push_back(make_pair(nr, nc));
                    }
                }
            }
        }
    }
    return islands;
}

JavaScript

var numIslands = function(grid) {
    const g = grid.map(function(r) { return r.slice(); });
    let count = 0;
    function sink(i, j) {
        if (i < 0 || j < 0 || i >= g.length || j >= g[0].length || g[i][j] !== 1) return;
        g[i][j] = 0;
        sink(i + 1, j);
        sink(i - 1, j);
        sink(i, j + 1);
        sink(i, j - 1);
    }
    for (let i = 0; i < g.length; i++) {
        for (let j = 0; j < g[0].length; j++) {
            if (g[i][j] === 1) {
                count++;
                sink(i, j);
            }
        }
    }
    return count;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium