mediumGraphs

Number of Islands

Count islands in a binary grid. Land cells contain 1 and connect horizontally or vertically; 0 is water.

LeetCode ↗

Work through the cases

3 examples

Input notation

Rows of a nonempty rectangular matrix, one space-separated row per line.

Expected result

The number of islands.

Case 1

Input

1 1 0
0 1 0
1 0 1

Expected output

Case 2

Input

0 0
0 0

Expected output

Case 3

Input

Expected output

These notes use simplified input/output notation. The linked platform defines the method signature and judge format.

FROM IDEA TO IMPLEMENTATION

Understand the approach.

Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.

Counting every cell with value 1 as its own island would double-count 4-connected land. With m,n ≤ 300, a full scan is acceptable, but each connected component must be cleared in one search. Adjacent land cells form one component, so a DFS from any unseen land cell covers the whole island. We scan the grid, start DFS at each 1, rewrite visited land to 0, and increment the answer once per search.

We can use depth-first search (DFS) to traverse each island. We iterate through each cell (i, j) in the grid. If the cell's value is '1', it means we have found a new island. We can start a DFS from this cell, marking all connected land cells as '0' to avoid duplicate counting. Each time we find a new island, we increment the island count by 1.

The time complexity is O(m × n), and the space complexity is O(m × n). Where m and n are the number of rows and columns in the grid, respectively.

class Solution {
    private char[][] grid;
    private int m;
    private int n;

    public int numIslands(char[][] grid) {
        m = grid.length;
        n = grid[0].length;
        this.grid = grid;
        int ans = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == '1') {
                    dfs(i, j);
                    ++ans;
                }
            }
        }
        return ans;
    }

    private void dfs(int i, int j) {
        grid[i][j] = '0';
        int[] dirs = {-1, 0, 1, 0, -1};
        for (int k = 0; k < 4; ++k) {
            int x = i + dirs[k];
            int y = j + dirs[k + 1];
            if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1') {
                dfs(x, y);
            }
        }
    }
}

Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.

Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.