Number of Islands

Medium Graphs Connected Components Original on LeetCode

Number of Islands is a medium graphs problem solved with the connected components pattern. The best approach, dfs sinking, runs in O(m · n) time and O(m · n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from bfs per island up.

Problem

Given a grid of '1' (land) and '0' (water), count the islands: groups of land cells connected horizontally or vertically.

Examples

Example 1

Input
grid = [[1,1,0,0],[1,0,0,1],[0,0,1,1]]
Output
2

Example 2

Input
grid = [[0,0],[0,0]]
Output
0

Constraints

  • 1 <= m, n <= 300; cells are '1' (land) or '0' (water).
  • 4-directional connectivity.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (2 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
BFS per islandO(m · n)O(min(m, n))
DFS sinkingO(m · n)O(m · n)

1BFS per island

TimeO(m · n)
SpaceO(min(m, n))The BFS frontier on a grid is bounded by its smaller side.

Scan the grid. On unvisited land, count an island and BFS to mark all its land.

  1. For each '1': count++, set it to '0', BFS setting neighbours to '0' when enqueued.
class Solution {
    public int numIslands(char[][] grid) {
        int m = grid.length, n = grid[0].length, count = 0;
        int[][] dirs = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++) {
                if (grid[i][j] != '1') continue;
                count++;
                grid[i][j] = '0';
                Queue<int[]> q = new ArrayDeque<>();
                q.add(new int[] { i, j });
                while (!q.isEmpty()) {
                    int[] c = q.poll();
                    for (int[] d : dirs) {
                        int r = c[0] + d[0], k = c[1] + d[1];
                        if (r >= 0 && k >= 0 && r < m && k < n && grid[r][k] == '1') {
                            grid[r][k] = '0';
                            q.add(new int[] { r, k });
                        }
                    }
                }
            }
        return count;
    }
}

2DFS sinking

TimeO(m · n)
SpaceO(m · n)Worst-case recursion depth when the grid is all land.

Same scan, but sink each island with a recursive DFS that turns its land into water.

  1. For each '1': count++, sink(i, j).
  2. sink: bounds and land check; set '0'; recurse 4 ways.
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++; sink(grid, i, j); }
        return count;
    }

    private void sink(char[][] g, int r, int c) {
        if (r < 0 || c < 0 || r >= g.length || c >= g[0].length || g[r][c] != '1') return;
        g[r][c] = '0';
        sink(g, r + 1, c);
        sink(g, r - 1, c);
        sink(g, r, c + 1);
        sink(g, r, c - 1);
    }
}

Edge cases to test

  • All water or all land
  • Islands touching only diagonally (separate)

Hints

Hint 1

Every time you find unvisited land, you have found a new island. Sink the whole island so you never count it again.

FAQ

What is the best time complexity for Number of Islands?

DFS sinking runs in O(m · n) time and O(m · n) extra space.

Which pattern does Number of Islands use?

It is a graphs problem that uses the connected components pattern. Other problems with the same pattern: Number of Provinces, Evaluate Division, Making A Large Island.

Is there a brute force solution for Number of Islands?

Yes. BFS per island takes O(m · n) time and O(min(m, n)) space. Scan the grid.

Which edge cases should I test for Number of Islands?

All water or all land; Islands touching only diagonally (separate).