Number of Islands II

Hard Graphs Connected Components Original on LeetCode

Reported atAmazonUberCRED

Number of Islands II is a hard graphs problem solved with the connected components pattern. The best approach, optimal (union-find with a running count), runs in O(m · n + k · α(m · n)) time and O(m · n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (recount after each addition) up.

Problem

You have an m x n map that starts as pure water. You are given a list positions; the i-th entry [r, c] turns the cell in row r, column c into land.

An island is a group of land cells connected horizontally or vertically (diagonal contact does not count). After each operation, record how many islands exist on the map.

Return the list of counts, one per operation, in order.

Examples

Example 1

Input
m = 3, n = 3, positions = [[0,0],[1,1],[0,1],[2,2],[1,2]]
Output
[1, 2, 1, 2, 1]
Why
(1,1) starts a second island, (0,1) joins both, (2,2) is new, and (1,2) links it to the big island.

Example 2

Input
m = 2, n = 3, positions = [[0,2],[1,0],[0,2],[1,1]]
Output
[1, 2, 2, 2]
Why
The third operation repeats (0,2), so nothing changes; (1,1) touches (1,0) only, so it extends that island.

Example 3

Input
m = 1, n = 1, positions = [[0,0]]
Output
[1]
Why
The only cell becomes land, giving one island.

Constraints

  • 1 <= m, n <= 10^4 and m * n <= 10^4
  • 1 <= positions.length <= 10^4
  • positions[i] = [r, c] with 0 <= r < m and 0 <= c < n
  • The same cell may appear more than once in positions.

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 (3 examples, or your own). Submit also runs 12 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.

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
Brute force (recount after each addition)O(k · m · n)O(m · n)
Optimal (union-find with a running count)O(m · n + k · α(m · n))O(m · n)

1Brute force (recount after each addition)

TimeO(k · m · n)k additions, and each one rescans the whole grid.
SpaceO(m · n)The grid, a visited array and the BFS queue.

Keep the grid. After turning each cell into land, run a full flood fill over the grid to count islands, and record that count.

  1. grid = m x n, all water.
  2. For each position: mark it as land.
  3. Count islands with BFS from every unvisited land cell; append the count.
class Solution {
    public List<Integer> numIslands2(int m, int n, int[][] positions) {
        boolean[][] land = new boolean[m][n];
        List<Integer> res = new ArrayList<>();
        int[][] dirs = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
        for (int[] p : positions) {
            land[p[0]][p[1]] = true;
            boolean[][] seen = new boolean[m][n];
            int count = 0;
            for (int i = 0; i < m; i++)
                for (int j = 0; j < n; j++) {
                    if (!land[i][j] || seen[i][j]) continue;
                    count++;
                    seen[i][j] = true;
                    ArrayDeque<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 && land[r][k] && !seen[r][k]) {
                                seen[r][k] = true;
                                q.add(new int[] { r, k });
                            }
                        }
                    }
                }
            res.add(count);
        }
        return res;
    }
}

2Optimal (union-find with a running count)

TimeO(m · n + k · α(m · n))Arrays are initialised once; each addition does at most 4 unions, each almost constant (α is the inverse Ackermann function).
SpaceO(m · n)The parent and size arrays have one slot per cell.

Give every cell an id r * n + c in a Disjoint Set Union. A new land cell adds one island. For each land neighbour, find both roots; if they differ, union them and subtract one island. A repeated cell changes nothing. Path compression and union by size make each operation almost O(1).

  1. parent[i] = -1 means water. On adding cell id: if already land, append count and continue.
  2. parent[id] = id, size[id] = 1, count++.
  3. For each of the 4 neighbours that is land: a = find(id), b = find(nb); if a != b, attach the smaller tree under the larger and count--.
  4. Append count.
class Solution {
    private int[] parent, size;

    public List<Integer> numIslands2(int m, int n, int[][] positions) {
        parent = new int[m * n];
        size = new int[m * n];
        Arrays.fill(parent, -1);
        List<Integer> res = new ArrayList<>();
        int[][] dirs = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
        int count = 0;
        for (int[] p : positions) {
            int id = p[0] * n + p[1];
            if (parent[id] != -1) { res.add(count); continue; }
            parent[id] = id;
            size[id] = 1;
            count++;
            for (int[] d : dirs) {
                int r = p[0] + d[0], c = p[1] + d[1];
                if (r < 0 || c < 0 || r >= m || c >= n) continue;
                int nb = r * n + c;
                if (parent[nb] == -1) continue;
                int a = find(id), b = find(nb);
                if (a == b) continue;
                if (size[a] < size[b]) { int t = a; a = b; b = t; }
                parent[b] = a;
                size[a] += size[b];
                count--;
            }
            res.add(count);
        }
        return res;
    }

    private int find(int x) {
        int root = x;
        while (parent[root] != root) root = parent[root];
        while (parent[x] != root) {
            int next = parent[x];
            parent[x] = root;
            x = next;
        }
        return root;
    }
}

Edge cases to test

  • A cell that is already land is added again (count stays the same)
  • One new cell that merges up to four different islands at once
  • Cells that touch only diagonally (still separate islands)
  • A grid that is a single row or a single column
  • Every cell of the grid eventually turned into land

Hints

Hint 1

After each addition you could recount islands from scratch, but that repeats almost all of the work every time.

Hint 2

A new land cell starts as its own island (+1). Each distinct neighbouring island it touches merges with it (-1 each).

Hint 3

A Disjoint Set Union (union-find) tells you in near O(1) whether two cells already belong to the same island, and merges them if not.

FAQ

What is the best time complexity for Number of Islands II?

Optimal (union-find with a running count) runs in O(m · n + k · α(m · n)) time and O(m · n) extra space. Arrays are initialised once; each addition does at most 4 unions, each almost constant (α is the inverse Ackermann function).

Which pattern does Number of Islands II use?

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

Is there a brute force solution for Number of Islands II?

Yes. Brute force (recount after each addition) takes O(k · m · n) time and O(m · n) space. Keep the grid.

Which edge cases should I test for Number of Islands II?

A cell that is already land is added again (count stays the same); One new cell that merges up to four different islands at once; Cells that touch only diagonally (still separate islands); A grid that is a single row or a single column; Every cell of the grid eventually turned into land.